QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#698881#5177. 摩斯电码 2.0TheZone100 ✓574ms5240kbC++2016.9kb2024-11-01 22:52:302024-11-01 22:52:32

Judging History

你现在查看的是最新测评结果

  • [2024-11-01 22:52:32]
  • 评测
  • 测评结果：100
  • 用时：574ms
  • 内存：5240kb
查看
  • [2024-11-01 22:52:30]
  • 提交

answer

#include <bits/stdc++.h>
#define FOR(i, l, r) for(int i = (l); i <= (r); i++)
#define ROF(i, r, l) for(int i = (r); i >= (l); i--)
#define sz(a) int((a).size())
#define ll long long
#define lll __int128
#define ull unsigned long long
#define vi vector<int>
#define pii pair<ll, ll>
using namespace std;
const int N = 1e5 + 10;
const ll oo = 6e9;
int n, m;
ll a[N], v[N], S;
struct node {
    ll sum, pre;
    node(ll sum = 0, ll pre = -oo) : sum(sum), pre(pre) {}
	friend node operator * (const node a, const node b) {
		return node(a.sum + b.sum, max(a.pre, a.sum + b.pre));
	}
	void operator *= (const node b){
		pre=max(pre,sum+b.pre);
		sum+=b.sum;
	}
	friend node operator ^ (node a, ll b) {
	//	node res;
	//	for(; b; b>>=1,a*=a) if(b & 1) res*=a;
	//	return res;
		if(!b) return node();
		if(a.sum>=0) return node(a.sum*b,a.pre+a.sum*(b-1));
		return node(a.sum*b,a.pre);
	}
	void operator ^=(ll b){
		if(!b) (*this)=node();
		else{
			if(sum>0)pre+=sum*(b-1);
			sum*=b;
		}
	}
};
node exgcd(ll a, ll b, ll c, ll n, node U, node R) {
//    b = (b % c + c) % c;
	if(a >= c) return exgcd(a % c, b, c, n, U, (U ^ a / c) * R);
	ll m = ((ll)a * n + b) / c;
	if(m == 0) return R ^= n,R;
	swap(U, R);
	node ans = (U ^ (c - b - 1) / a);
	ans *= R;
	ans *= exgcd(c, (c - b - 1)%a, a, m - 1, U, R);
	ans *= (U ^ (n - ((ll) m * c - b - 1) / a));
	return ans;
}
ll calc(ll a, ll x, ll c, ll now) {
    node U(-c, -oo), R(x, x), S(now, now);
    S = S * exgcd(x, now%c, c, a, U, R);
    return S.pre;
}
int check(int x) {
    ll now = 0, sum = 0;
    ll lim = m * S;
    FOR(i, 1, n - 1) {
        sum += (v[i] + a[i]) * x - S;
        if(sum >= 0 && sum > lim) return 0;
    }
    sum += (S - 1) * (n - 1);
    FOR(i, 1, n - 1) {
        now += v[i] * x - 1;
        now %= S;
        ll mx = calc(a[i], x, S, now);
        sum -= mx;
        if(x + sum / S <= m) return 1;
        now = (now + a[i] * x + S - mx) % S;
    }
    assert(sum % S == 0);
    if(x + sum / S <= m) return 1;
    return 0;
}
int main() {
    ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    FOR(i, 0, n - 1) cin >> v[i];
    FOR(i, 0, n - 1) cin >> a[i];
    S = v[0] + a[0], a[0] = 0;
    S += a[n - 1], a[n - 1] = 0;
    int l = 1, r = m, x = 0;
    while(l <= r) {
        int mid = (l + r) / 2;
        if(check(mid)) x = mid, l = mid + 1;
        else r = mid - 1;
    }
    cout << x << "\n";
	return 0;
}
/*#include <bits/stdc++.h>
#define FOR(i, l, r) for(int i = (l); i <= (r); i++)
#define ROF(i, r, l) for(int i = (r); i >= (l); i--)
#define sz(a) int((a).size())
#define ll long long
#define lll __int128
#define ull unsigned long long
#define vi vector<int>
#define pii pair<ll, ll>
using namespace std;
const int N = 1e5 + 10;
const ll oo = 6e9;
int n, m;
ll a[N], v[N], S;
struct node {
    ll sum, pre;
    node(ll sum = 0, ll pre = -oo) : sum(sum), pre(pre) {}
	friend node operator * (const node a, const node b) {
		return node(a.sum + b.sum, max(a.pre, a.sum + b.pre));
	}
	void operator *= (const node b){
		pre=max(pre,sum+b.pre);
		sum+=b.sum;
	}
	friend node operator ^ (node a, ll b) {
	//	node res;
	//	for(; b; b>>=1,a*=a) if(b & 1) res*=a;
	//	return res;
		if(!b) return node();
		if(a.sum>=0) return node(a.sum*b,a.pre+a.sum*(b-1));
		return node(a.sum*b,a.pre);
	}
	void operator ^=(ll b){
		if(!b) (*this)=node();
		else{
			if(sum>0)pre+=sum*(b-1);
			sum*=b;
		}
	}
};
node exgcd(ll a, ll b, ll c, ll n, node U, node R) {
//    b = (b % c + c) % c;
	if(a >= c) return exgcd(a % c, b, c, n, U, (U ^ a / c) * R);
	ll m = ((ll)a * n + b) / c;
	if(m == 0) return R ^= n,R;
	swap(U, R);
	node ans = (U ^ (c - b - 1) / a);
	ans *= R;
	ans *= exgcd(c, (c - b - 1)%a, a, m - 1, U, R);
	ans *= (U ^ (n - ((ll) m * c - b - 1) / a));
	return ans;
}
ll calc(ll a, ll x, ll c, ll now) {
    node U(-c, -oo), R(x, x), S(now, now);
    S = S * exgcd(x, now%c, c, a, U, R);
    return S.pre;
}
int check(int x) {
    ll now = 0, sum = 0;
    ll lim = m * S;
    FOR(i, 1, n - 1) {
        sum += (v[i] + a[i]) * x - S;
        if(sum >= 0 && sum > lim) return 0;
    }
    sum += (S - 1) * (n - 1);
    FOR(i, 1, n - 1) {
        now += v[i] * x - 1;
        now %= S;
        ll mx = calc(a[i], x, S, now);
        sum -= mx;
        if(x + sum / S <= m) return 1;
        now = (now + a[i] * x + S - mx) % S;
    }
    assert(sum % S == 0);
    if(x + sum / S <= m) return 1;
    return 0;
}
int main() {
    ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    FOR(i, 0, n - 1) cin >> v[i];
    FOR(i, 0, n - 1) cin >> a[i];
    S = v[0] + a[0], a[0] = 0;
    S += a[n - 1], a[n - 1] = 0;
    int l = 1, r = m, x = 0;
    while(l <= r) {
        int mid = (l + r) / 2;
        if(check(mid)) x = mid, l = mid + 1;
        else r = mid - 1;
    }
    cout << x << "\n";
	return 0;
}#include <bits/stdc++.h>
#define FOR(i, l, r) for(int i = (l); i <= (r); i++)
#define ROF(i, r, l) for(int i = (r); i >= (l); i--)
#define sz(a) int((a).size())
#define ll long long
#define lll __int128
#define ull unsigned long long
#define vi vector<int>
#define pii pair<ll, ll>
using namespace std;
const int N = 1e5 + 10;
const ll oo = 6e9;
int n, m;
ll a[N], v[N], S;
struct node {
    ll sum, pre;
    node(ll sum = 0, ll pre = -oo) : sum(sum), pre(pre) {}
	friend node operator * (const node a, const node b) {
		return node(a.sum + b.sum, max(a.pre, a.sum + b.pre));
	}
	void operator *= (const node b){
		pre=max(pre,sum+b.pre);
		sum+=b.sum;
	}
	friend node operator ^ (node a, ll b) {
	//	node res;
	//	for(; b; b>>=1,a*=a) if(b & 1) res*=a;
	//	return res;
		if(!b) return node();
		if(a.sum>=0) return node(a.sum*b,a.pre+a.sum*(b-1));
		return node(a.sum*b,a.pre);
	}
	void operator ^=(ll b){
		if(!b) (*this)=node();
		else{
			if(sum>0)pre+=sum*(b-1);
			sum*=b;
		}
	}
};
node exgcd(ll a, ll b, ll c, ll n, node U, node R) {
//    b = (b % c + c) % c;
	if(a >= c) return exgcd(a % c, b, c, n, U, (U ^ a / c) * R);
	ll m = ((ll)a * n + b) / c;
	if(m == 0) return R ^= n,R;
	swap(U, R);
	node ans = (U ^ (c - b - 1) / a);
	ans *= R;
	ans *= exgcd(c, (c - b - 1)%a, a, m - 1, U, R);
	ans *= (U ^ (n - ((ll) m * c - b - 1) / a));
	return ans;
}
ll calc(ll a, ll x, ll c, ll now) {
    node U(-c, -oo), R(x, x), S(now, now);
    S = S * exgcd(x, now%c, c, a, U, R);
    return S.pre;
}
int check(int x) {
    ll now = 0, sum = 0;
    ll lim = m * S;
    FOR(i, 1, n - 1) {
        sum += (v[i] + a[i]) * x - S;
        if(sum >= 0 && sum > lim) return 0;
    }
    sum += (S - 1) * (n - 1);
    FOR(i, 1, n - 1) {
        now += v[i] * x - 1;
        now %= S;
        ll mx = calc(a[i], x, S, now);
        sum -= mx;
        if(x + sum / S <= m) return 1;
        now = (now + a[i] * x + S - mx) % S;
    }
    assert(sum % S == 0);
    if(x + sum / S <= m) return 1;
    return 0;
}
int main() {
    ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    FOR(i, 0, n - 1) cin >> v[i];
    FOR(i, 0, n - 1) cin >> a[i];
    S = v[0] + a[0], a[0] = 0;
    S += a[n - 1], a[n - 1] = 0;
    int l = 1, r = m, x = 0;
    while(l <= r) {
        int mid = (l + r) / 2;
        if(check(mid)) x = mid, l = mid + 1;
        else r = mid - 1;
    }
    cout << x << "\n";
	return 0;
}#include <bits/stdc++.h>
#define FOR(i, l, r) for(int i = (l); i <= (r); i++)
#define ROF(i, r, l) for(int i = (r); i >= (l); i--)
#define sz(a) int((a).size())
#define ll long long
#define lll __int128
#define ull unsigned long long
#define vi vector<int>
#define pii pair<ll, ll>
using namespace std;
const int N = 1e5 + 10;
const ll oo = 6e9;
int n, m;
ll a[N], v[N], S;
struct node {
    ll sum, pre;
    node(ll sum = 0, ll pre = -oo) : sum(sum), pre(pre) {}
	friend node operator * (const node a, const node b) {
		return node(a.sum + b.sum, max(a.pre, a.sum + b.pre));
	}
	void operator *= (const node b){
		pre=max(pre,sum+b.pre);
		sum+=b.sum;
	}
	friend node operator ^ (node a, ll b) {
	//	node res;
	//	for(; b; b>>=1,a*=a) if(b & 1) res*=a;
	//	return res;
		if(!b) return node();
		if(a.sum>=0) return node(a.sum*b,a.pre+a.sum*(b-1));
		return node(a.sum*b,a.pre);
	}
	void operator ^=(ll b){
		if(!b) (*this)=node();
		else{
			if(sum>0)pre+=sum*(b-1);
			sum*=b;
		}
	}
};
node exgcd(ll a, ll b, ll c, ll n, node U, node R) {
//    b = (b % c + c) % c;
	if(a >= c) return exgcd(a % c, b, c, n, U, (U ^ a / c) * R);
	ll m = ((ll)a * n + b) / c;
	if(m == 0) return R ^= n,R;
	swap(U, R);
	node ans = (U ^ (c - b - 1) / a);
	ans *= R;
	ans *= exgcd(c, (c - b - 1)%a, a, m - 1, U, R);
	ans *= (U ^ (n - ((ll) m * c - b - 1) / a));
	return ans;
}
ll calc(ll a, ll x, ll c, ll now) {
    node U(-c, -oo), R(x, x), S(now, now);
    S = S * exgcd(x, now%c, c, a, U, R);
    return S.pre;
}
int check(int x) {
    ll now = 0, sum = 0;
    ll lim = m * S;
    FOR(i, 1, n - 1) {
        sum += (v[i] + a[i]) * x - S;
        if(sum >= 0 && sum > lim) return 0;
    }
    sum += (S - 1) * (n - 1);
    FOR(i, 1, n - 1) {
        now += v[i] * x - 1;
        now %= S;
        ll mx = calc(a[i], x, S, now);
        sum -= mx;
        if(x + sum / S <= m) return 1;
        now = (now + a[i] * x + S - mx) % S;
    }
    assert(sum % S == 0);
    if(x + sum / S <= m) return 1;
    return 0;
}
int main() {
    ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    FOR(i, 0, n - 1) cin >> v[i];
    FOR(i, 0, n - 1) cin >> a[i];
    S = v[0] + a[0], a[0] = 0;
    S += a[n - 1], a[n - 1] = 0;
    int l = 1, r = m, x = 0;
    while(l <= r) {
        int mid = (l + r) / 2;
        if(check(mid)) x = mid, l = mid + 1;
        else r = mid - 1;
    }
    cout << x << "\n";
	return 0;
}#include <bits/stdc++.h>
#define FOR(i, l, r) for(int i = (l); i <= (r); i++)
#define ROF(i, r, l) for(int i = (r); i >= (l); i--)
#define sz(a) int((a).size())
#define ll long long
#define lll __int128
#define ull unsigned long long
#define vi vector<int>
#define pii pair<ll, ll>
using namespace std;
const int N = 1e5 + 10;
const ll oo = 6e9;
int n, m;
ll a[N], v[N], S;
struct node {
    ll sum, pre;
    node(ll sum = 0, ll pre = -oo) : sum(sum), pre(pre) {}
	friend node operator * (const node a, const node b) {
		return node(a.sum + b.sum, max(a.pre, a.sum + b.pre));
	}
	void operator *= (const node b){
		pre=max(pre,sum+b.pre);
		sum+=b.sum;
	}
	friend node operator ^ (node a, ll b) {
	//	node res;
	//	for(; b; b>>=1,a*=a) if(b & 1) res*=a;
	//	return res;
		if(!b) return node();
		if(a.sum>=0) return node(a.sum*b,a.pre+a.sum*(b-1));
		return node(a.sum*b,a.pre);
	}
	void operator ^=(ll b){
		if(!b) (*this)=node();
		else{
			if(sum>0)pre+=sum*(b-1);
			sum*=b;
		}
	}
};
node exgcd(ll a, ll b, ll c, ll n, node U, node R) {
//    b = (b % c + c) % c;
	if(a >= c) return exgcd(a % c, b, c, n, U, (U ^ a / c) * R);
	ll m = ((ll)a * n + b) / c;
	if(m == 0) return R ^= n,R;
	swap(U, R);
	node ans = (U ^ (c - b - 1) / a);
	ans *= R;
	ans *= exgcd(c, (c - b - 1)%a, a, m - 1, U, R);
	ans *= (U ^ (n - ((ll) m * c - b - 1) / a));
	return ans;
}
ll calc(ll a, ll x, ll c, ll now) {
    node U(-c, -oo), R(x, x), S(now, now);
    S = S * exgcd(x, now%c, c, a, U, R);
    return S.pre;
}
int check(int x) {
    ll now = 0, sum = 0;
    ll lim = m * S;
    FOR(i, 1, n - 1) {
        sum += (v[i] + a[i]) * x - S;
        if(sum >= 0 && sum > lim) return 0;
    }
    sum += (S - 1) * (n - 1);
    FOR(i, 1, n - 1) {
        now += v[i] * x - 1;
        now %= S;
        ll mx = calc(a[i], x, S, now);
        sum -= mx;
        if(x + sum / S <= m) return 1;
        now = (now + a[i] * x + S - mx) % S;
    }
    assert(sum % S == 0);
    if(x + sum / S <= m) return 1;
    return 0;
}
int main() {
    ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    FOR(i, 0, n - 1) cin >> v[i];
    FOR(i, 0, n - 1) cin >> a[i];
    S = v[0] + a[0], a[0] = 0;
    S += a[n - 1], a[n - 1] = 0;
    int l = 1, r = m, x = 0;
    while(l <= r) {
        int mid = (l + r) / 2;
        if(check(mid)) x = mid, l = mid + 1;
        else r = mid - 1;
    }
    cout << x << "\n";
	return 0;
}#include <bits/stdc++.h>
#define FOR(i, l, r) for(int i = (l); i <= (r); i++)
#define ROF(i, r, l) for(int i = (r); i >= (l); i--)
#define sz(a) int((a).size())
#define ll long long
#define lll __int128
#define ull unsigned long long
#define vi vector<int>
#define pii pair<ll, ll>
using namespace std;
const int N = 1e5 + 10;
const ll oo = 6e9;
int n, m;
ll a[N], v[N], S;
struct node {
    ll sum, pre;
    node(ll sum = 0, ll pre = -oo) : sum(sum), pre(pre) {}
	friend node operator * (const node a, const node b) {
		return node(a.sum + b.sum, max(a.pre, a.sum + b.pre));
	}
	void operator *= (const node b){
		pre=max(pre,sum+b.pre);
		sum+=b.sum;
	}
	friend node operator ^ (node a, ll b) {
	//	node res;
	//	for(; b; b>>=1,a*=a) if(b & 1) res*=a;
	//	return res;
		if(!b) return node();
		if(a.sum>=0) return node(a.sum*b,a.pre+a.sum*(b-1));
		return node(a.sum*b,a.pre);
	}
	void operator ^=(ll b){
		if(!b) (*this)=node();
		else{
			if(sum>0)pre+=sum*(b-1);
			sum*=b;
		}
	}
};
node exgcd(ll a, ll b, ll c, ll n, node U, node R) {
//    b = (b % c + c) % c;
	if(a >= c) return exgcd(a % c, b, c, n, U, (U ^ a / c) * R);
	ll m = ((ll)a * n + b) / c;
	if(m == 0) return R ^= n,R;
	swap(U, R);
	node ans = (U ^ (c - b - 1) / a);
	ans *= R;
	ans *= exgcd(c, (c - b - 1)%a, a, m - 1, U, R);
	ans *= (U ^ (n - ((ll) m * c - b - 1) / a));
	return ans;
}
ll calc(ll a, ll x, ll c, ll now) {
    node U(-c, -oo), R(x, x), S(now, now);
    S = S * exgcd(x, now%c, c, a, U, R);
    return S.pre;
}
int check(int x) {
    ll now = 0, sum = 0;
    ll lim = m * S;
    FOR(i, 1, n - 1) {
        sum += (v[i] + a[i]) * x - S;
        if(sum >= 0 && sum > lim) return 0;
    }
    sum += (S - 1) * (n - 1);
    FOR(i, 1, n - 1) {
        now += v[i] * x - 1;
        now %= S;
        ll mx = calc(a[i], x, S, now);
        sum -= mx;
        if(x + sum / S <= m) return 1;
        now = (now + a[i] * x + S - mx) % S;
    }
    assert(sum % S == 0);
    if(x + sum / S <= m) return 1;
    return 0;
}
int main() {
    ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    FOR(i, 0, n - 1) cin >> v[i];
    FOR(i, 0, n - 1) cin >> a[i];
    S = v[0] + a[0], a[0] = 0;
    S += a[n - 1], a[n - 1] = 0;
    int l = 1, r = m, x = 0;
    while(l <= r) {
        int mid = (l + r) / 2;
        if(check(mid)) x = mid, l = mid + 1;
        else r = mid - 1;
    }
    cout << x << "\n";
	return 0;
}#include <bits/stdc++.h>
#define FOR(i, l, r) for(int i = (l); i <= (r); i++)
#define ROF(i, r, l) for(int i = (r); i >= (l); i--)
#define sz(a) int((a).size())
#define ll long long
#define lll __int128
#define ull unsigned long long
#define vi vector<int>
#define pii pair<ll, ll>
using namespace std;
const int N = 1e5 + 10;
const ll oo = 6e9;
int n, m;
ll a[N], v[N], S;
struct node {
    ll sum, pre;
    node(ll sum = 0, ll pre = -oo) : sum(sum), pre(pre) {}
	friend node operator * (const node a, const node b) {
		return node(a.sum + b.sum, max(a.pre, a.sum + b.pre));
	}
	void operator *= (const node b){
		pre=max(pre,sum+b.pre);
		sum+=b.sum;
	}
	friend node operator ^ (node a, ll b) {
	//	node res;
	//	for(; b; b>>=1,a*=a) if(b & 1) res*=a;
	//	return res;
		if(!b) return node();
		if(a.sum>=0) return node(a.sum*b,a.pre+a.sum*(b-1));
		return node(a.sum*b,a.pre);
	}
	void operator ^=(ll b){
		if(!b) (*this)=node();
		else{
			if(sum>0)pre+=sum*(b-1);
			sum*=b;
		}
	}
};
node exgcd(ll a, ll b, ll c, ll n, node U, node R) {
//    b = (b % c + c) % c;
	if(a >= c) return exgcd(a % c, b, c, n, U, (U ^ a / c) * R);
	ll m = ((ll)a * n + b) / c;
	if(m == 0) return R ^= n,R;
	swap(U, R);
	node ans = (U ^ (c - b - 1) / a);
	ans *= R;
	ans *= exgcd(c, (c - b - 1)%a, a, m - 1, U, R);
	ans *= (U ^ (n - ((ll) m * c - b - 1) / a));
	return ans;
}
ll calc(ll a, ll x, ll c, ll now) {
    node U(-c, -oo), R(x, x), S(now, now);
    S = S * exgcd(x, now%c, c, a, U, R);
    return S.pre;
}
int check(int x) {
    ll now = 0, sum = 0;
    ll lim = m * S;
    FOR(i, 1, n - 1) {
        sum += (v[i] + a[i]) * x - S;
        if(sum >= 0 && sum > lim) return 0;
    }
    sum += (S - 1) * (n - 1);
    FOR(i, 1, n - 1) {
        now += v[i] * x - 1;
        now %= S;
        ll mx = calc(a[i], x, S, now);
        sum -= mx;
        if(x + sum / S <= m) return 1;
        now = (now + a[i] * x + S - mx) % S;
    }
    assert(sum % S == 0);
    if(x + sum / S <= m) return 1;
    return 0;
}
int main() {
    ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
        else r = mid - 1;
    }
    cout << x << "\n";
	return 0;
}*/
源文件, 语言: C++20

詳細信息

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 0ms
memory: 3620kb

input:

5 5
2 5 5 4 3
2 4 4 5 5

output:

2

result:

ok single line: '2'

Test #2:

score: 10
Accepted
time: 0ms
memory: 3664kb

input:

5 5
2 2 1 3 2
1 4 1 5 1

output:

1

result:

ok single line: '1'

Test #3:

score: 10
Accepted
time: 0ms
memory: 3616kb

input:

5 5
4 5 1 4 3
4 5 1 2 5

output:

3

result:

ok single line: '3'

Test #4:

score: 10
Accepted
time: 0ms
memory: 3620kb

input:

5 4
5 2 5 1 1
0 3 0 0 0

output:

2

result:

ok single line: '2'

Subtask #2:

score: 10
Accepted

Test #5:

score: 10
Accepted
time: 0ms
memory: 3736kb

input:

5 38
170 62 7 129 93
39 98 2 178 110

output:

15

result:

ok single line: '15'

Test #6:

score: 10
Accepted
time: 0ms
memory: 3616kb

input:

9 75
175 240 5 139 127 216 66 128 121
94 204 150 150 50 66 26 225 142

output:

14

result:

ok single line: '14'

Test #7:

score: 10
Accepted
time: 0ms
memory: 3616kb

input:

4 81
99 122 93 175
210 91 93 20

output:

30

result:

ok single line: '30'

Test #8:

score: 10
Accepted
time: 0ms
memory: 3732kb

input:

50 4
249 124 249 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 125 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

output:

2

result:

ok single line: '2'

Subtask #3:

score: 20
Accepted

Test #9:

score: 20
Accepted
time: 0ms
memory: 3744kb

input:

50 340
145945353 943649879 103681368 412537460 249168929 368424447 732376003 185334999 144319344 511521494 159409847 131972188 193314434 725004712 439570846 364294834 362411427 314220847 829136416 305293003 505373341 638710304 851245152 521859350 644327541 974583375 738591681 147795709 922157319 421...

output:

1

result:

ok single line: '1'

Test #10:

score: 20
Accepted
time: 0ms
memory: 3680kb

input:

50 4
812930736 95702098 665441738 221300735 907249385 493535187 564488639 395538786 904638787 889168971 900357003 21636011 764504998 243769369 89695414 656445453 745884937 656421159 296885639 206987195 368396912 54679316 346974906 192974419 56304682 420269636 396600899 473826419 708845531 57105109 5...

output:

2

result:

ok single line: '2'

Test #11:

score: 20
Accepted
time: 0ms
memory: 3700kb

input:

50 242
21994377 883494624 811211287 2014707 690537081 642841499 847215492 156177058 39805037 586706497 747465489 685773253 531808559 229539707 496349943 951616271 871232872 203160652 315507929 814504770 613932493 843612050 706827895 664552255 385267680 711345437 661256346 598502814 135899412 8864698...

output:

3

result:

ok single line: '3'

Test #12:

score: 20
Accepted
time: 0ms
memory: 3708kb

input:

50 4
999999999 499999999 999999999 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 500000000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

output:

2

result:

ok single line: '2'

Subtask #4:

score: 20
Accepted

Test #13:

score: 20
Accepted
time: 1ms
memory: 3700kb

input:

1000 1000
1000000000 732930495 57470406 998674942 980507254 200197125 826994891 726235561 146440304 908089621 108786784 22006340 629816450 656110319 505896602 620885446 857656443 30603288 902307001 946990065 915078227 237356805 675986931 241912445 489230924 199892606 129509547 544771174 171477200 39...

output:

5

result:

ok single line: '5'

Test #14:

score: 20
Accepted
time: 1ms
memory: 3704kb

input:

1000 1000
1000000000 453471409 905614634 806348886 981162692 631439224 930083764 404360418 24967881 160576315 801671665 34036350 696442318 773463170 948012795 632483513 663699140 631713699 242910304 674688351 657952373 731872077 509942253 617068591 566333397 907505014 415703394 97229594 62543056 759...

output:

5

result:

ok single line: '5'

Test #15:

score: 20
Accepted
time: 1ms
memory: 3716kb

input:

1000 1000
1000000000 291747303 422386015 257592899 327122383 190971251 608849610 652627969 663681554 841402690 663081454 292908449 47703356 516750918 64219158 926051265 621570037 799236461 6245888 849103506 825735179 15976866 546795144 97837445 984902727 273742478 827728137 881712379 19536116 302228...

output:

3

result:

ok single line: '3'

Test #16:

score: 20
Accepted
time: 1ms
memory: 3696kb

input:

1000 4
999999999 499999999 999999999 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

2

result:

ok single line: '2'

Subtask #5:

score: 20
Accepted

Test #17:

score: 20
Accepted
time: 26ms
memory: 3896kb

input:

10000 1000000000
1000000000 9322 8270 4220 4967 6470 2768 7780 590 1436 4219 7804 8549 8916 9250 1420 5911 2115 7098 9942 4217 7430 5121 4217 395 1363 1098 3314 2058 6689 3270 6734 6663 2769 7773 5406 5705 1208 4409 6282 5593 7665 1334 6208 1138 6856 4597 2152 3666 5645 6841 1182 8469 1768 9165 4521...

output:

952514052

result:

ok single line: '952514052'

Test #18:

score: 20
Accepted
time: 37ms
memory: 3840kb

input:

10000 1000000000
1000000000 3275 8344 5026 8794 8765 6000 2106 9868 4292 8406 3796 6770 8206 5003 4598 7852 5817 1122 1013 8496 107 6159 9237 3629 9978 311 7318 8825 1662 3437 7462 4557 4867 5170 8804 3918 2599 8362 2306 6675 8704 8048 4123 4324 4478 5153 6429 3437 5451 8262 6603 9291 7355 7675 7785...

output:

952638019

result:

ok single line: '952638019'

Test #19:

score: 20
Accepted
time: 30ms
memory: 3856kb

input:

10000 1000000000
1000000000 9340 2411 8503 7659 8627 8236 9143 2644 9106 8942 692 4499 961 8312 7145 2791 7081 381 3920 1929 8007 7091 709 662 2170 9266 7611 8404 6689 3320 1652 1637 7040 9862 2683 2076 4205 4528 2677 9356 4458 4354 3586 2509 2669 1336 5576 757 4803 5771 6376 7022 4390 9306 5353 375...

output:

952249748

result:

ok single line: '952249748'

Test #20:

score: 20
Accepted
time: 1ms
memory: 3896kb

input:

10000 4
999999999 499999999 999999999 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

2

result:

ok single line: '2'

Subtask #6:

score: 20
Accepted

Test #21:

score: 20
Accepted
time: 284ms
memory: 5236kb

input:

100000 1000000000
1000000000 34788 73380 66152 92356 82130 69036 96709 88944 26043 93630 93922 79818 18546 43338 40621 46994 77235 61925 24567 63929 22345 8049 40400 68808 79834 10769 68961 415 75455 73445 65121 66981 39924 45321 66260 43977 81382 98200 6894 11936 10781 29304 45584 12022 26163 73225...

output:

166625645

result:

ok single line: '166625645'

Test #22:

score: 20
Accepted
time: 412ms
memory: 5240kb

input:

100000 1000000000
1000000000 75957 29362 79932 93815 8663 70095 16669 56934 17206 42916 22440 98520 7351 77617 78869 11288 66476 72652 94320 24268 18187 76937 13012 7061 88367 452 27910 16042 29210 48683 69545 14205 44290 26006 90050 75978 30731 88472 22700 19598 36904 92430 12180 43948 19316 9460 9...

output:

166873954

result:

ok single line: '166873954'

Test #23:

score: 20
Accepted
time: 352ms
memory: 5168kb

input:

100000 1000000000
1000000000 39963 23621 63615 37801 71944 31559 92776 88006 42234 27017 3884 86410 79373 50270 85989 87055 75601 48689 73512 19912 78874 40976 44608 36804 99092 57525 6218 83980 72089 42778 34848 85018 49750 63915 77867 80585 22481 79232 75696 77786 20667 65988 47543 3328 10398 9643...

output:

166489682

result:

ok single line: '166489682'

Test #24:

score: 20
Accepted
time: 574ms
memory: 5204kb

input:

100000 1000000000
1000000000 90037 96630 38282 80048 7468 68500 78306 71502 6708 66919 4350 16795 35905 6338 77065 69708 53050 7113 74997 92255 27593 71915 41797 11832 54047 52532 23584 25541 51672 30969 70431 73764 48968 70276 9731 33423 24010 93191 76723 25998 59151 7291 74787 17574 97622 69865 15...

output:

166994702

result:

ok single line: '166994702'

Test #25:

score: 20
Accepted
time: 4ms
memory: 5176kb

input:

100000 4
999999999 499999999 999999999 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

2

result:

ok single line: '2'
English 繁體中文 简体中文

伺服器時間: 2024-12-02 13:03:55 | 開源專案