답안 #979979

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
979979	2024-05-11T18:30:22 Z	vjudge1	축구 경기장 (IOI23_soccer)	C++17	65.5 / 100	353 ms	79128 KB

soccer

// hola soy Dember :D
// 31/03/2024

#include <bits/stdc++.h>

#define ll int 
#define pll pair<ll,ll>
#define F first
#define S second 
#define Z size()
#define pb push_back
#define bp pop_back
#define fo(x,y,z) for(ll x=y; x<=z; x++)
#define of(x,y,z) for(ll x=y; x>=z; x--)
#define all(n) n.begin(), n.end()
#define arr(x,y,z) x+y, x+y+z

using namespace std;

void value(ll in){cout<<((in)?"YES\n":"NO\n");}

ll n, m, k, xd[505], zd[505], tt[505];
ll ans;
vector<vector<ll>> iz, A, res;
vector<ll> dp;
vector<pll> r;
set<ll> f;
queue<ll> q;

vector<ll> cl(ll p){
    vector<ll> st, v(n+1);
    ll x;
    fo(i,0,n-1)v[i]=i;
    
    fo(i,0,n-1){
        x=i;
        
        while(!st.empty() && iz[st.back()][p]<=iz[i][p]){x=st.back();st.pop_back();}
        
        st.push_back(i);
        v[i]=v[x];
    }
    return v;
}

vector<ll> cr(ll p){
    vector<ll> st, v(n+1);
    ll x;
    fo(i,0,n-1)v[i]=i;
    
    of(i,n-1,0){
        x=i;
        
        while(!st.empty() && iz[st.back()][p]<=iz[i][p]){x=st.back();st.pop_back();}
        
        st.push_back(i);
        v[i]=v[x];
    }
    return v;
}

void CD(ll p){
    vector<ll> a, b, c(n+1), d;r.clear();
    
    a=cl(p);
    b=cr(p);
    
    fo(i,0,n-1)c[i]=b[i]-a[i]+1;
    
    fo(i,0,n-1){
        if(!A[i][p])r.pb({iz[i][p], i});
        xd[i]=i-1;zd[i]=i+1;
    }zd[n-1]=-1;
    
    sort(all(r));
    
    for(auto u:r)dp[u.S]+=(c[u.S]-tt[u.S])*(p-iz[u.S][p]);
    
    for(auto u:r){
        if(xd[u.S]>=0)dp[xd[u.S]]=max(dp[xd[u.S]],(c[xd[u.S]]-c[u.S])*(p-iz[xd[u.S]][p])+dp[u.S]);
        if(zd[u.S]>=0)dp[zd[u.S]]=max(dp[zd[u.S]],(c[zd[u.S]]-c[u.S])*(p-iz[zd[u.S]][p])+dp[u.S]);
        if(zd[u.S]!=-1)xd[zd[u.S]]=xd[u.S];
        if(xd[u.S]!=-1)zd[xd[u.S]]=zd[u.S];
        
        tt[u.S]=c[u.S];
    }
    
    res.pb(dp);
    for(auto u:dp)ans=max(ans, u);
    fo(i,0,n-1) if(A[i][p])dp[i]=tt[i]=0;
    
    return;
}

int biggest_stadium(int N, vector<vector<int>> ola){
    n=N;iz.resize(n+1,vector<ll>(n+1,-1));A=ola;dp.resize(n+1,0);
    
    fo(i,0,n-1){
        fo(j,0,n-1){
            if(A[i][j])iz[i][j]=j;
            else if(j>0)iz[i][j]=iz[i][j-1];
        }
    }
    
    of(h,n-1,0)CD(h);
    
    return ans;
}

/*int main()
{
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    
    int t=1; 
    cin>>t;
    
    vector<vector<int>> ola(t+1,vector<int> (t+1));
    fo(i,0,t-1)
        fo(j,0,t-1)cin>>ola[i][j];
    
    cout<<biggest_stadium(t, ola)<<"\n";
    
    fo(i,0,n-1){
        fo(j,0,n-1)cout<<res[i][j]<<' ';cout<<"\n";
    }

    return 0;
}*/

Subtask #0
0.0 / 0.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	344 KB	ok

Subtask #1
1.5 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	ok
2	Correct	0 ms	348 KB	ok
3	Correct	1 ms	348 KB	ok
4	Correct	0 ms	348 KB	ok
5	Correct	0 ms	348 KB	ok
6	Correct	0 ms	348 KB	ok
7	Correct	2 ms	604 KB	ok
8	Correct	25 ms	5252 KB	ok
9	Partially correct	294 ms	78888 KB	partial

Subtask #2
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	ok
2	Correct	0 ms	348 KB	ok
3	Correct	0 ms	344 KB	ok
4	Correct	0 ms	348 KB	ok
5	Correct	0 ms	348 KB	ok
6	Correct	1 ms	348 KB	ok
7	Correct	0 ms	348 KB	ok
8	Correct	0 ms	348 KB	ok
9	Correct	0 ms	348 KB	ok
10	Correct	1 ms	348 KB	ok
11	Correct	0 ms	348 KB	ok
12	Correct	0 ms	348 KB	ok
13	Correct	1 ms	348 KB	ok

Subtask #3
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	344 KB	ok
2	Correct	0 ms	348 KB	ok
3	Correct	0 ms	348 KB	ok
4	Correct	0 ms	344 KB	ok
5	Correct	0 ms	348 KB	ok
6	Correct	0 ms	348 KB	ok
7	Correct	1 ms	348 KB	ok
8	Correct	0 ms	348 KB	ok
9	Correct	0 ms	348 KB	ok
10	Correct	0 ms	348 KB	ok
11	Correct	1 ms	348 KB	ok
12	Correct	0 ms	348 KB	ok
13	Correct	0 ms	348 KB	ok
14	Correct	1 ms	348 KB	ok
15	Correct	0 ms	348 KB	ok
16	Correct	0 ms	348 KB	ok
17	Correct	0 ms	600 KB	ok
18	Correct	0 ms	348 KB	ok
19	Correct	0 ms	348 KB	ok
20	Correct	0 ms	348 KB	ok
21	Correct	0 ms	348 KB	ok
22	Correct	0 ms	348 KB	ok
23	Correct	1 ms	348 KB	ok
24	Correct	1 ms	348 KB	ok
25	Correct	0 ms	348 KB	ok
26	Correct	0 ms	344 KB	ok

Subtask #4
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	344 KB	ok
2	Correct	0 ms	348 KB	ok
3	Correct	0 ms	348 KB	ok
4	Correct	1 ms	348 KB	ok
5	Correct	0 ms	348 KB	ok
6	Correct	0 ms	344 KB	ok
7	Correct	0 ms	348 KB	ok
8	Correct	0 ms	348 KB	ok
9	Correct	1 ms	348 KB	ok
10	Correct	0 ms	348 KB	ok
11	Correct	0 ms	348 KB	ok
12	Correct	0 ms	348 KB	ok
13	Correct	1 ms	348 KB	ok
14	Correct	0 ms	348 KB	ok
15	Correct	0 ms	348 KB	ok
16	Correct	1 ms	348 KB	ok
17	Correct	0 ms	348 KB	ok
18	Correct	0 ms	348 KB	ok
19	Correct	0 ms	600 KB	ok
20	Correct	0 ms	348 KB	ok
21	Correct	0 ms	348 KB	ok
22	Correct	0 ms	348 KB	ok
23	Correct	0 ms	348 KB	ok
24	Correct	0 ms	348 KB	ok
25	Correct	1 ms	348 KB	ok
26	Correct	1 ms	348 KB	ok
27	Correct	0 ms	348 KB	ok
28	Correct	0 ms	344 KB	ok
29	Correct	1 ms	344 KB	ok
30	Correct	1 ms	348 KB	ok
31	Correct	0 ms	348 KB	ok
32	Correct	1 ms	348 KB	ok
33	Correct	1 ms	388 KB	ok
34	Correct	1 ms	756 KB	ok
35	Correct	1 ms	348 KB	ok
36	Correct	0 ms	348 KB	ok
37	Correct	0 ms	348 KB	ok
38	Correct	1 ms	344 KB	ok
39	Correct	0 ms	348 KB	ok
40	Correct	0 ms	348 KB	ok
41	Correct	1 ms	348 KB	ok

Subtask #5
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	344 KB	ok
2	Correct	0 ms	348 KB	ok
3	Correct	0 ms	348 KB	ok
4	Correct	1 ms	348 KB	ok
5	Correct	0 ms	348 KB	ok
6	Correct	0 ms	344 KB	ok
7	Correct	0 ms	348 KB	ok
8	Correct	0 ms	348 KB	ok
9	Correct	1 ms	348 KB	ok
10	Correct	0 ms	348 KB	ok
11	Correct	0 ms	348 KB	ok
12	Correct	0 ms	348 KB	ok
13	Correct	1 ms	348 KB	ok
14	Correct	0 ms	348 KB	ok
15	Correct	0 ms	348 KB	ok
16	Correct	1 ms	348 KB	ok
17	Correct	0 ms	348 KB	ok
18	Correct	0 ms	348 KB	ok
19	Correct	0 ms	600 KB	ok
20	Correct	0 ms	348 KB	ok
21	Correct	0 ms	348 KB	ok
22	Correct	0 ms	348 KB	ok
23	Correct	0 ms	348 KB	ok
24	Correct	0 ms	348 KB	ok
25	Correct	1 ms	348 KB	ok
26	Correct	1 ms	348 KB	ok
27	Correct	0 ms	348 KB	ok
28	Correct	0 ms	344 KB	ok
29	Correct	1 ms	344 KB	ok
30	Correct	1 ms	348 KB	ok
31	Correct	0 ms	348 KB	ok
32	Correct	1 ms	348 KB	ok
33	Correct	1 ms	388 KB	ok
34	Correct	1 ms	756 KB	ok
35	Correct	1 ms	348 KB	ok
36	Correct	0 ms	348 KB	ok
37	Correct	0 ms	348 KB	ok
38	Correct	1 ms	344 KB	ok
39	Correct	0 ms	348 KB	ok
40	Correct	0 ms	348 KB	ok
41	Correct	1 ms	348 KB	ok
42	Correct	39 ms	5304 KB	ok
43	Correct	37 ms	5212 KB	ok
44	Correct	37 ms	5204 KB	ok
45	Correct	34 ms	5204 KB	ok
46	Correct	39 ms	5272 KB	ok
47	Correct	27 ms	5204 KB	ok
48	Correct	24 ms	5212 KB	ok
49	Correct	29 ms	5616 KB	ok
50	Correct	24 ms	5204 KB	ok
51	Correct	29 ms	5212 KB	ok
52	Correct	20 ms	5212 KB	ok
53	Correct	19 ms	5212 KB	ok
54	Correct	21 ms	5208 KB	ok
55	Correct	22 ms	5316 KB	ok
56	Correct	21 ms	5384 KB	ok
57	Correct	32 ms	5200 KB	ok
58	Correct	27 ms	5212 KB	ok
59	Correct	29 ms	5208 KB	ok

Subtask #6
0.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	344 KB	ok
2	Correct	0 ms	348 KB	ok
3	Correct	0 ms	348 KB	ok
4	Correct	1 ms	348 KB	ok
5	Correct	0 ms	348 KB	ok
6	Correct	0 ms	348 KB	ok
7	Correct	0 ms	348 KB	ok
8	Correct	2 ms	604 KB	ok
9	Correct	25 ms	5252 KB	ok
10	Partially correct	294 ms	78888 KB	partial
11	Correct	0 ms	344 KB	ok
12	Correct	0 ms	348 KB	ok
13	Correct	0 ms	348 KB	ok
14	Correct	1 ms	348 KB	ok
15	Correct	0 ms	348 KB	ok
16	Correct	0 ms	348 KB	ok
17	Correct	0 ms	348 KB	ok
18	Correct	1 ms	348 KB	ok
19	Correct	0 ms	348 KB	ok
20	Correct	0 ms	348 KB	ok
21	Correct	1 ms	348 KB	ok
22	Correct	0 ms	348 KB	ok
23	Correct	0 ms	348 KB	ok
24	Correct	0 ms	600 KB	ok
25	Correct	0 ms	348 KB	ok
26	Correct	0 ms	348 KB	ok
27	Correct	0 ms	348 KB	ok
28	Correct	0 ms	348 KB	ok
29	Correct	0 ms	348 KB	ok
30	Correct	1 ms	348 KB	ok
31	Correct	1 ms	348 KB	ok
32	Correct	0 ms	348 KB	ok
33	Correct	0 ms	344 KB	ok
34	Correct	1 ms	344 KB	ok
35	Correct	1 ms	348 KB	ok
36	Correct	0 ms	348 KB	ok
37	Correct	1 ms	348 KB	ok
38	Correct	1 ms	388 KB	ok
39	Correct	1 ms	756 KB	ok
40	Correct	1 ms	348 KB	ok
41	Correct	0 ms	348 KB	ok
42	Correct	0 ms	348 KB	ok
43	Correct	1 ms	344 KB	ok
44	Correct	0 ms	348 KB	ok
45	Correct	0 ms	348 KB	ok
46	Correct	1 ms	348 KB	ok
47	Correct	39 ms	5304 KB	ok
48	Correct	37 ms	5212 KB	ok
49	Correct	37 ms	5204 KB	ok
50	Correct	34 ms	5204 KB	ok
51	Correct	39 ms	5272 KB	ok
52	Correct	27 ms	5204 KB	ok
53	Correct	24 ms	5212 KB	ok
54	Correct	29 ms	5616 KB	ok
55	Correct	24 ms	5204 KB	ok
56	Correct	29 ms	5212 KB	ok
57	Correct	20 ms	5212 KB	ok
58	Correct	19 ms	5212 KB	ok
59	Correct	21 ms	5208 KB	ok
60	Correct	22 ms	5316 KB	ok
61	Correct	21 ms	5384 KB	ok
62	Correct	32 ms	5200 KB	ok
63	Correct	27 ms	5212 KB	ok
64	Correct	29 ms	5208 KB	ok
65	Partially correct	353 ms	79128 KB	partial
66	Runtime error	311 ms	78872 KB	Execution killed with signal 11
67	Halted	0 ms	0 KB	-

답안 #979979

Compilation message

Subtask #0 0.0 / 0.0

Subtask #1 1.5 / 6.0

Subtask #2 8.0 / 8.0

Subtask #3 22.0 / 22.0

Subtask #4 18.0 / 18.0

Subtask #5 16.0 / 16.0

Subtask #6 0.0 / 30.0

Subtask #0
0.0 / 0.0

Subtask #1
1.5 / 6.0

Subtask #2
8.0 / 8.0

Subtask #3
22.0 / 22.0

Subtask #4
18.0 / 18.0

Subtask #5
16.0 / 16.0

Subtask #6
0.0 / 30.0