oj.uz

Submission #840166

# Submission time Handle Problem Language Result Execution time Memory
840166 2023-08-31T07:39:56 Z KLPP Soccer Stadium (IOI23_soccer) C++17
64 / 100
 3946 ms 550524 KB 
#include "soccer.h"
#include<bits/stdc++.h>

using namespace std;
typedef long long int lld;

#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
int table[2000][2000];
int n;
int pref[50][50];
vector<pair<int,int> >inter[1000][1000];
int tot[1000];
vector<lld> ans[1000][1000];
int biggest_stadium(int N, std::vector<std::vector<int>> F)
{
    n=N;
    rep(i,0,n){
		rep(j,0,n){
			table[i][j]=F[i][j];
		}
	}
	rep(i,0,n){
		rep(i,0,n)tot[i]=0;
		rep(j,i,n){
			rep(k,0,n)tot[k]+=table[j][k];
			int lst=-1;
			rep(k,0,n+1){
				if(k==n || tot[k]>0){
					if(k-lst>=2){
						inter[i][j].push_back({k-1,lst+1});
					}
					lst=k;
				}
			}
			ans[i][j].resize(inter[i][j].size(),0);
		}
	}
	for(int diff=n-1;diff>0;diff--){
		for(int i=0;i+diff<n;i++){
			int j=i+diff;
			rep(k,0,(int)inter[i][j].size()){
				int pos1=lower_bound(inter[i][j-1].begin(),inter[i][j-1].end(),pair<int,int>(inter[i][j][k].first,-1e9))-inter[i][j-1].begin();
				ans[i][j-1][pos1]=max(ans[i][j-1][pos1],ans[i][j][k]+inter[i][j][k].first-inter[i][j][k].second+1);
				//cout<<i<<" "<<j<<" "<<inter[i][j][k].first<<" "<<inter[i][j][k].second<<" "<<inter[i][j-1][pos1].first<<" "<<inter[i][j-1][pos1].second<<endl;
				pos1=lower_bound(inter[i+1][j].begin(),inter[i+1][j].end(),pair<int,int>(inter[i][j][k].first,-1e9))-inter[i+1][j].begin();
				ans[i+1][j][pos1]=max(ans[i+1][j][pos1],ans[i][j][k]+inter[i][j][k].first-inter[i][j][k].second+1);
			}
		}
	}
	lld res=0;
	rep(i,0,n){
		rep(k,0,(int)(inter[i][i].size())){
			res=max(res,ans[i][i][k]+inter[i][i][k].first-inter[i][i][k].second+1);
		}
	}
	return res;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 47312 KB ok

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47176 KB ok
2 Correct 19 ms 47188 KB ok
3 Correct 19 ms 47320 KB ok
4 Correct 20 ms 47316 KB ok
5 Correct 21 ms 47188 KB ok
6 Correct 19 ms 47212 KB ok
7 Correct 22 ms 48084 KB ok
8 Correct 122 ms 59980 KB ok
9 Runtime error 3946 ms 378088 KB Execution killed with signal 6
10 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47176 KB ok
2 Correct 19 ms 47188 KB ok
3 Correct 23 ms 47188 KB ok
4 Correct 26 ms 47188 KB ok
5 Correct 20 ms 47188 KB ok
6 Correct 21 ms 47176 KB ok
7 Correct 19 ms 47188 KB ok
8 Correct 19 ms 47188 KB ok
9 Correct 19 ms 47188 KB ok
10 Correct 22 ms 47220 KB ok
11 Correct 23 ms 47172 KB ok
12 Correct 19 ms 47188 KB ok
13 Correct 25 ms 47188 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 47312 KB ok
2 Correct 21 ms 47176 KB ok
3 Correct 19 ms 47188 KB ok
4 Correct 23 ms 47188 KB ok
5 Correct 26 ms 47188 KB ok
6 Correct 20 ms 47188 KB ok
7 Correct 21 ms 47176 KB ok
8 Correct 19 ms 47188 KB ok
9 Correct 19 ms 47188 KB ok
10 Correct 19 ms 47188 KB ok
11 Correct 22 ms 47220 KB ok
12 Correct 23 ms 47172 KB ok
13 Correct 19 ms 47188 KB ok
14 Correct 25 ms 47188 KB ok
15 Correct 18 ms 47236 KB ok
16 Correct 18 ms 47276 KB ok
17 Correct 24 ms 47224 KB ok
18 Correct 20 ms 47188 KB ok
19 Correct 18 ms 47188 KB ok
20 Correct 18 ms 47188 KB ok
21 Correct 19 ms 47188 KB ok
22 Correct 19 ms 47188 KB ok
23 Correct 19 ms 47316 KB ok
24 Correct 23 ms 47188 KB ok
25 Correct 21 ms 47188 KB ok
26 Correct 24 ms 47336 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 47312 KB ok
2 Correct 21 ms 47176 KB ok
3 Correct 19 ms 47188 KB ok
4 Correct 19 ms 47320 KB ok
5 Correct 20 ms 47316 KB ok
6 Correct 23 ms 47188 KB ok
7 Correct 26 ms 47188 KB ok
8 Correct 20 ms 47188 KB ok
9 Correct 21 ms 47176 KB ok
10 Correct 19 ms 47188 KB ok
11 Correct 19 ms 47188 KB ok
12 Correct 19 ms 47188 KB ok
13 Correct 22 ms 47220 KB ok
14 Correct 23 ms 47172 KB ok
15 Correct 19 ms 47188 KB ok
16 Correct 25 ms 47188 KB ok
17 Correct 18 ms 47236 KB ok
18 Correct 18 ms 47276 KB ok
19 Correct 24 ms 47224 KB ok
20 Correct 20 ms 47188 KB ok
21 Correct 18 ms 47188 KB ok
22 Correct 18 ms 47188 KB ok
23 Correct 19 ms 47188 KB ok
24 Correct 19 ms 47188 KB ok
25 Correct 19 ms 47316 KB ok
26 Correct 23 ms 47188 KB ok
27 Correct 21 ms 47188 KB ok
28 Correct 24 ms 47336 KB ok
29 Correct 22 ms 47304 KB ok
30 Correct 20 ms 47408 KB ok
31 Correct 20 ms 47444 KB ok
32 Correct 20 ms 47316 KB ok
33 Correct 20 ms 47316 KB ok
34 Correct 19 ms 47420 KB ok
35 Correct 19 ms 47316 KB ok
36 Correct 19 ms 47316 KB ok
37 Correct 19 ms 47316 KB ok
38 Correct 19 ms 47316 KB ok
39 Correct 22 ms 47368 KB ok
40 Correct 22 ms 47316 KB ok
41 Correct 19 ms 47316 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 47312 KB ok
2 Correct 21 ms 47176 KB ok
3 Correct 19 ms 47188 KB ok
4 Correct 19 ms 47320 KB ok
5 Correct 20 ms 47316 KB ok
6 Correct 23 ms 47188 KB ok
7 Correct 26 ms 47188 KB ok
8 Correct 20 ms 47188 KB ok
9 Correct 21 ms 47176 KB ok
10 Correct 19 ms 47188 KB ok
11 Correct 19 ms 47188 KB ok
12 Correct 19 ms 47188 KB ok
13 Correct 22 ms 47220 KB ok
14 Correct 23 ms 47172 KB ok
15 Correct 19 ms 47188 KB ok
16 Correct 25 ms 47188 KB ok
17 Correct 18 ms 47236 KB ok
18 Correct 18 ms 47276 KB ok
19 Correct 24 ms 47224 KB ok
20 Correct 20 ms 47188 KB ok
21 Correct 18 ms 47188 KB ok
22 Correct 18 ms 47188 KB ok
23 Correct 19 ms 47188 KB ok
24 Correct 19 ms 47188 KB ok
25 Correct 19 ms 47316 KB ok
26 Correct 23 ms 47188 KB ok
27 Correct 21 ms 47188 KB ok
28 Correct 24 ms 47336 KB ok
29 Correct 22 ms 47304 KB ok
30 Correct 20 ms 47408 KB ok
31 Correct 20 ms 47444 KB ok
32 Correct 20 ms 47316 KB ok
33 Correct 20 ms 47316 KB ok
34 Correct 19 ms 47420 KB ok
35 Correct 19 ms 47316 KB ok
36 Correct 19 ms 47316 KB ok
37 Correct 19 ms 47316 KB ok
38 Correct 19 ms 47316 KB ok
39 Correct 22 ms 47368 KB ok
40 Correct 22 ms 47316 KB ok
41 Correct 19 ms 47316 KB ok
42 Correct 228 ms 73812 KB ok
43 Correct 184 ms 62516 KB ok
44 Correct 588 ms 210636 KB ok
45 Correct 664 ms 261276 KB ok
46 Correct 302 ms 101280 KB ok
47 Correct 158 ms 69648 KB ok
48 Correct 158 ms 59768 KB ok
49 Correct 137 ms 59272 KB ok
50 Correct 1450 ms 550524 KB ok
51 Correct 146 ms 58856 KB ok
52 Correct 151 ms 54624 KB ok
53 Correct 119 ms 52860 KB ok
54 Correct 142 ms 54984 KB ok
55 Correct 140 ms 58572 KB ok
56 Correct 164 ms 54108 KB ok
57 Correct 136 ms 60108 KB ok
58 Correct 146 ms 59980 KB ok
59 Correct 151 ms 59804 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 47312 KB ok
2 Correct 21 ms 47176 KB ok
3 Correct 19 ms 47188 KB ok
4 Correct 19 ms 47320 KB ok
5 Correct 20 ms 47316 KB ok
6 Correct 21 ms 47188 KB ok
7 Correct 19 ms 47212 KB ok
8 Correct 22 ms 48084 KB ok
9 Correct 122 ms 59980 KB ok
10 Runtime error 3946 ms 378088 KB Execution killed with signal 6
11 Halted 0 ms 0 KB -