Submission #290460

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
290460	2020-09-03T20:36:41 Z	MatheusLealV	Bigger segments (IZhO19_segments)	C++17	27 / 100	83 ms	23052 KB

segments

#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
using namespace std;

#define int long long
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
ll mod = (1000000007LL);
inline ll Mod(ll a, ll b){return (a%b);}
inline ll poww(ll a, ll b){ll res = 1;while (b > 0){if(b & 1) res = (res * a)%mod;a = (a * a)%mod;b >>= 1;}return res;}
ll gcd (ll a, ll b) { while (b) { a %= b,swap(a, b);}return a;}
void read(vector<int> &w, int n){w.resize(n);for(int i = 0; i < n; i++) cin>>w[i];}
void print(vector<int> &w){for(int i =0; i < sz(w); i++){if(i == sz(w) - 1) cout<<w[i]<<"\n";else cout<<w[i]<<" ";}}
int prodmod(vector<int> w);
int summod(vector<int> w);
///CUIDADO COM MAXN
#define N 300050

int n, m, q, k, v[N], ans;
pii w[N];
string s;
int vis[510][510];
int dp[510][510], pref[N];
int solve(int i, int h){
	if(i > n) return 0;
	if(vis[i][h]) return dp[i][h];
	int prev = pref[i-1]-pref[h-1];
	vis[i][h] = 1;
	int ans = -2000000;
	for(int j = i; j <= n; j++){
		if(pref[j] - pref[i-1] >= prev){
			ans = max(ans,1 + solve(j + 1, i));
		}
	}
	return dp[i][h] = ans;
}
int32_t main(){
	ios::sync_with_stdio(false); cin.tie(0);
	cin>>n;
	for(int i = 1; i <= n; i++){
		cin>>v[i];
		pref[i] = pref[i-1] + v[i];
	}
	cout<<solve(1, 1)<<"\n";
}
/*
    CUIDADO COM MAXN, MOD, OVERFLOW 
    >Colocar (>DEFINE INT LONG LONG<) no inicio do template
    >mod = (1e9 + 7), por padrao (NAO ESQUECER DE ALTERAR)
    >NAO ESQUECER DEFINE INT LONG LONG
    > N = 1 ? 
*/
int summod(vector<int> w){int curr=0;for(int i=0;i<sz(w); i++){curr = (curr+w[i])%mod;if(curr<0)curr+=mod;}return curr;}
int prodmod(vector<int> w){int curr = 1;
for(int i = 0; i < sz(w); i++){if(w[i] >= mod) w[i] %= mod;curr = (curr * w[i]) % mod;if(curr < 0) curr += mod;}return curr;}

Subtask #1
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	1 ms	512 KB	Output is correct
5	Correct	1 ms	512 KB	Output is correct
6	Correct	1 ms	512 KB	Output is correct
7	Correct	1 ms	512 KB	Output is correct
8	Correct	0 ms	384 KB	Output is correct
9	Correct	0 ms	512 KB	Output is correct
10	Correct	1 ms	512 KB	Output is correct
11	Correct	1 ms	512 KB	Output is correct
12	Correct	1 ms	512 KB	Output is correct
13	Correct	1 ms	512 KB	Output is correct
14	Correct	0 ms	512 KB	Output is correct
15	Correct	0 ms	512 KB	Output is correct

Subtask #2
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	1 ms	512 KB	Output is correct
5	Correct	1 ms	512 KB	Output is correct
6	Correct	1 ms	512 KB	Output is correct
7	Correct	1 ms	512 KB	Output is correct
8	Correct	0 ms	384 KB	Output is correct
9	Correct	0 ms	512 KB	Output is correct
10	Correct	1 ms	512 KB	Output is correct
11	Correct	1 ms	512 KB	Output is correct
12	Correct	1 ms	512 KB	Output is correct
13	Correct	1 ms	512 KB	Output is correct
14	Correct	0 ms	512 KB	Output is correct
15	Correct	0 ms	512 KB	Output is correct
16	Correct	3 ms	4352 KB	Output is correct
17	Correct	42 ms	4344 KB	Output is correct
18	Correct	60 ms	4344 KB	Output is correct
19	Correct	49 ms	4344 KB	Output is correct
20	Correct	66 ms	4472 KB	Output is correct
21	Correct	58 ms	4344 KB	Output is correct
22	Correct	32 ms	3584 KB	Output is correct
23	Correct	14 ms	2816 KB	Output is correct
24	Correct	60 ms	4344 KB	Output is correct
25	Correct	60 ms	4320 KB	Output is correct
26	Correct	83 ms	4348 KB	Output is correct
27	Correct	31 ms	4352 KB	Output is correct
28	Correct	73 ms	4344 KB	Output is correct
29	Correct	76 ms	4344 KB	Output is correct
30	Correct	66 ms	4420 KB	Output is correct

Subtask #3
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	1 ms	512 KB	Output is correct
5	Correct	1 ms	512 KB	Output is correct
6	Correct	1 ms	512 KB	Output is correct
7	Correct	1 ms	512 KB	Output is correct
8	Correct	0 ms	384 KB	Output is correct
9	Correct	0 ms	512 KB	Output is correct
10	Correct	1 ms	512 KB	Output is correct
11	Correct	1 ms	512 KB	Output is correct
12	Correct	1 ms	512 KB	Output is correct
13	Correct	1 ms	512 KB	Output is correct
14	Correct	0 ms	512 KB	Output is correct
15	Correct	0 ms	512 KB	Output is correct
16	Correct	3 ms	4352 KB	Output is correct
17	Correct	42 ms	4344 KB	Output is correct
18	Correct	60 ms	4344 KB	Output is correct
19	Correct	49 ms	4344 KB	Output is correct
20	Correct	66 ms	4472 KB	Output is correct
21	Correct	58 ms	4344 KB	Output is correct
22	Correct	32 ms	3584 KB	Output is correct
23	Correct	14 ms	2816 KB	Output is correct
24	Correct	60 ms	4344 KB	Output is correct
25	Correct	60 ms	4320 KB	Output is correct
26	Correct	83 ms	4348 KB	Output is correct
27	Correct	31 ms	4352 KB	Output is correct
28	Correct	73 ms	4344 KB	Output is correct
29	Correct	76 ms	4344 KB	Output is correct
30	Correct	66 ms	4420 KB	Output is correct
31	Runtime error	29 ms	23052 KB	Execution killed with signal 11
32	Halted	0 ms	0 KB	-

Subtask #4
0 / 36.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	1 ms	512 KB	Output is correct
5	Correct	1 ms	512 KB	Output is correct
6	Correct	1 ms	512 KB	Output is correct
7	Correct	1 ms	512 KB	Output is correct
8	Correct	0 ms	384 KB	Output is correct
9	Correct	0 ms	512 KB	Output is correct
10	Correct	1 ms	512 KB	Output is correct
11	Correct	1 ms	512 KB	Output is correct
12	Correct	1 ms	512 KB	Output is correct
13	Correct	1 ms	512 KB	Output is correct
14	Correct	0 ms	512 KB	Output is correct
15	Correct	0 ms	512 KB	Output is correct
16	Correct	3 ms	4352 KB	Output is correct
17	Correct	42 ms	4344 KB	Output is correct
18	Correct	60 ms	4344 KB	Output is correct
19	Correct	49 ms	4344 KB	Output is correct
20	Correct	66 ms	4472 KB	Output is correct
21	Correct	58 ms	4344 KB	Output is correct
22	Correct	32 ms	3584 KB	Output is correct
23	Correct	14 ms	2816 KB	Output is correct
24	Correct	60 ms	4344 KB	Output is correct
25	Correct	60 ms	4320 KB	Output is correct
26	Correct	83 ms	4348 KB	Output is correct
27	Correct	31 ms	4352 KB	Output is correct
28	Correct	73 ms	4344 KB	Output is correct
29	Correct	76 ms	4344 KB	Output is correct
30	Correct	66 ms	4420 KB	Output is correct
31	Runtime error	29 ms	23052 KB	Execution killed with signal 11
32	Halted	0 ms	0 KB	-

Subtask #5
0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	1 ms	512 KB	Output is correct
5	Correct	1 ms	512 KB	Output is correct
6	Correct	1 ms	512 KB	Output is correct
7	Correct	1 ms	512 KB	Output is correct
8	Correct	0 ms	384 KB	Output is correct
9	Correct	0 ms	512 KB	Output is correct
10	Correct	1 ms	512 KB	Output is correct
11	Correct	1 ms	512 KB	Output is correct
12	Correct	1 ms	512 KB	Output is correct
13	Correct	1 ms	512 KB	Output is correct
14	Correct	0 ms	512 KB	Output is correct
15	Correct	0 ms	512 KB	Output is correct
16	Correct	3 ms	4352 KB	Output is correct
17	Correct	42 ms	4344 KB	Output is correct
18	Correct	60 ms	4344 KB	Output is correct
19	Correct	49 ms	4344 KB	Output is correct
20	Correct	66 ms	4472 KB	Output is correct
21	Correct	58 ms	4344 KB	Output is correct
22	Correct	32 ms	3584 KB	Output is correct
23	Correct	14 ms	2816 KB	Output is correct
24	Correct	60 ms	4344 KB	Output is correct
25	Correct	60 ms	4320 KB	Output is correct
26	Correct	83 ms	4348 KB	Output is correct
27	Correct	31 ms	4352 KB	Output is correct
28	Correct	73 ms	4344 KB	Output is correct
29	Correct	76 ms	4344 KB	Output is correct
30	Correct	66 ms	4420 KB	Output is correct
31	Runtime error	29 ms	23052 KB	Execution killed with signal 11
32	Halted	0 ms	0 KB	-

Submission #290460

Compilation message

Subtask #1 13.0 / 13.0

Subtask #2 14.0 / 14.0

Subtask #3 0 / 10.0

Subtask #4 0 / 36.0

Subtask #5 0 / 27.0

Subtask #1
13.0 / 13.0

Subtask #2
14.0 / 14.0

Subtask #3
0 / 10.0

Subtask #4
0 / 36.0

Subtask #5
0 / 27.0