oj.uz

답안 #403896

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
403896 2021-05-13T14:43:51 Z Fidisk Solar Storm (NOI20_solarstorm) C++14
62 / 100
 455 ms 254660 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define oo 1e15
#define fi first
#define se second
#define sp(iiii) setprecision(iiii)
#define IO ios_base::sync_with_stdio(false); cin.tie(0)
#define ms(aaaa,xxxx) memset(aaaa,xxxx,sizeof(aaaa))
#define cntbit(xxxx) __builtin_popcount(xxxx)
#define getbit(xxxx,aaaa) ((xxxx>>(aaaa-1))&1)
 
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<pair<int,int>,int> piii;
typedef pair<long long,long long> pll;
typedef pair<pair<long long,long long>,long long> plll;
typedef pair<pair<long long,long long>,pair<long long,long long>> pllll;
typedef pair<pair<long long,long long>,bool> pllb;
 
const ll base=361;
const ll mod=998244353;
const ld eps=1e-5;
const ll maxn=1e6;
 
ll n,s,k,res,pos,sum[19][1000009],pre[1000009],a[1000009],ans;
int g[19][1000009],r[1000009],l[1000009],v[1000009],p[1000009],i,j;
 
ll calc(int x,int y) {
    ll kq=0;
  	if (getbit(y,19)==1) {
      	kq+=sum[18][x];
      	x=g[18][x];
      	kq+=sum[18][x];
      	x=g[18][x];
    }
    for (ll ii=18;ii>=0;ii--) {
        if (getbit(y,ii+1)==1) {
            kq+=sum[ii][x];
            x=g[ii][x];
        }
    }
    return kq;
}
 
void Trace(ll x,ll y) {
    if (y==s) {
        cout<<s<<'\n';
        return;
    }
    if (x==n+1) {
        cout<<y<<'\n';
        return;
    }
    Trace(r[p[x]]+1,y+1);
    cout<<p[x]<<' ';
}
 
int main(){
    IO;
    cin>>n>>s>>k;
    for (i=1;i<n;i++) {
        cin>>a[i+1];
        a[i+1]+=a[i];
    }
    for (i=1;i<=n;i++) {
        cin>>v[i];
    }
    for (i=n;i>0;i--) {
        ans=i;
        for (j=ans-1;j>0;j/=2) {
            while (ans-j>0&&a[ans-j]>=a[i]-k) {
                ans-=j;
            }
        }
        l[i]=ans;
        p[l[i]]=max(p[l[i]],i);
    }
    for (i=1;i<=n;i++) {
        ans=i;
        for (j=n;j>0;j/=2) {
            while (ans+j<=n&&a[ans+j]<=a[i]+k) {
                ans+=j;
            }
        }
        r[i]=ans;
    }
    for (i=1;i<=n;i++) {
        p[i]=max(p[i-1],p[i]);
    }
    for (i=1;i<=n;i++) {
        pre[i]=pre[i-1]+v[i];
    }
    for (i=1;i<=n;i++) {
        g[0][i]=r[p[i]]+1;
    }
    g[0][n+1]=n+1;
    sum[0][n+1]=0;
    for (i=1;i<=n;i++) {
        sum[0][i]=pre[g[0][i]-1]-pre[i-1];
    }
    for (i=1;i<=18;i++) {
        for (j=1;j<=n+1;j++) {
            g[i][j]=g[i-1][g[i-1][j]];
            sum[i][j]=sum[i-1][j]+sum[i-1][g[i-1][j]];
        }
    }
    //cout<<k<<'\n';
    for (i=1;i<=n;i++) {
        ans=calc(i,s)-sum[0][i]+pre[r[p[i]]]-pre[l[p[i]]-1];
        if (ans>res) {
            //cout<<ans<<' '<<res<<' '<<i<<' '<<p[i]<<'\n';
            res=ans;
            pos=i;
        }
    }
    //cout<<res<<'\n';
    Trace(pos,0);
    return 0;
    for (i=1;i<=n;i++) {
        cout<<a[i]<<' ';
    }
    cout<<'\n';
    for (i=1;i<=n;i++) {
        cout<<p[i]<<' ';
    }
    cout<<'\n';
    for (i=1;i<=n;i++) {
        cout<<l[i]<<' ';
    }
    cout<<'\n';
    for (i=1;i<=n;i++) {
        cout<<r[i]<<' ';
    }
    cout<<'\n';
    for (i=1;i<=n;i++) {
        cout<<pre[i]<<' ';
    }
    cout<<'\n';
    for (i=1;i<=n;i++) {
        cout<<g[1][i]<<' ';
    }
    cout<<'\n';
 
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 5 ms 2892 KB Output is correct
3 Correct 5 ms 3148 KB Output is correct
4 Correct 3 ms 1740 KB Output is correct
5 Correct 1 ms 648 KB Output is correct
6 Correct 4 ms 2636 KB Output is correct
7 Correct 5 ms 2764 KB Output is correct
8 Correct 5 ms 3148 KB Output is correct
9 Correct 4 ms 2252 KB Output is correct
10 Correct 5 ms 3020 KB Output is correct
11 Correct 5 ms 3148 KB Output is correct
12 Correct 3 ms 1612 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 384 ms 218692 KB Output is correct
2 Correct 269 ms 139288 KB Output is correct
3 Correct 275 ms 149200 KB Output is correct
4 Correct 272 ms 162712 KB Output is correct
5 Correct 325 ms 190640 KB Output is correct
6 Correct 436 ms 254056 KB Output is correct
7 Correct 284 ms 167936 KB Output is correct

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 5 ms 2892 KB Output is correct
3 Correct 5 ms 3148 KB Output is correct
4 Correct 3 ms 1740 KB Output is correct
5 Correct 1 ms 648 KB Output is correct
6 Correct 4 ms 2636 KB Output is correct
7 Correct 5 ms 2764 KB Output is correct
8 Correct 5 ms 3148 KB Output is correct
9 Correct 4 ms 2252 KB Output is correct
10 Correct 5 ms 3020 KB Output is correct
11 Correct 5 ms 3148 KB Output is correct
12 Correct 3 ms 1612 KB Output is correct
13 Correct 384 ms 218692 KB Output is correct
14 Correct 269 ms 139288 KB Output is correct
15 Correct 275 ms 149200 KB Output is correct
16 Correct 272 ms 162712 KB Output is correct
17 Correct 325 ms 190640 KB Output is correct
18 Correct 436 ms 254056 KB Output is correct
19 Correct 284 ms 167936 KB Output is correct
20 Correct 270 ms 139020 KB Output is correct
21 Correct 315 ms 170360 KB Output is correct
22 Correct 357 ms 202096 KB Output is correct
23 Correct 396 ms 208204 KB Output is correct
24 Correct 383 ms 188176 KB Output is correct
25 Correct 377 ms 188224 KB Output is correct
26 Correct 280 ms 140312 KB Output is correct
27 Correct 371 ms 180200 KB Output is correct
28 Correct 348 ms 178116 KB Output is correct
29 Correct 440 ms 231392 KB Output is correct
30 Correct 350 ms 189380 KB Output is correct
31 Correct 298 ms 166132 KB Output is correct

Subtask #4
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 366 ms 217076 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 5 ms 2892 KB Output is correct
3 Correct 5 ms 3148 KB Output is correct
4 Correct 3 ms 1740 KB Output is correct
5 Correct 1 ms 648 KB Output is correct
6 Correct 4 ms 2636 KB Output is correct
7 Correct 5 ms 2764 KB Output is correct
8 Correct 5 ms 3148 KB Output is correct
9 Correct 4 ms 2252 KB Output is correct
10 Correct 5 ms 3020 KB Output is correct
11 Correct 5 ms 3148 KB Output is correct
12 Correct 3 ms 1612 KB Output is correct
13 Correct 6 ms 3148 KB Output is correct
14 Correct 4 ms 2636 KB Output is correct
15 Correct 4 ms 2544 KB Output is correct
16 Correct 3 ms 1996 KB Output is correct
17 Correct 4 ms 2508 KB Output is correct
18 Correct 5 ms 3020 KB Output is correct
19 Correct 4 ms 2636 KB Output is correct
20 Correct 4 ms 2252 KB Output is correct
21 Correct 6 ms 3708 KB Output is correct
22 Correct 5 ms 3148 KB Output is correct
23 Correct 5 ms 3020 KB Output is correct
24 Correct 5 ms 2764 KB Output is correct
25 Correct 6 ms 2936 KB Output is correct
26 Correct 5 ms 2912 KB Output is correct
27 Correct 4 ms 2380 KB Output is correct
28 Correct 5 ms 2508 KB Output is correct
29 Correct 4 ms 2636 KB Output is correct
30 Correct 7 ms 3032 KB Output is correct

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 5 ms 2892 KB Output is correct
3 Correct 5 ms 3148 KB Output is correct
4 Correct 3 ms 1740 KB Output is correct
5 Correct 1 ms 648 KB Output is correct
6 Correct 4 ms 2636 KB Output is correct
7 Correct 5 ms 2764 KB Output is correct
8 Correct 5 ms 3148 KB Output is correct
9 Correct 4 ms 2252 KB Output is correct
10 Correct 5 ms 3020 KB Output is correct
11 Correct 5 ms 3148 KB Output is correct
12 Correct 3 ms 1612 KB Output is correct
13 Correct 384 ms 218692 KB Output is correct
14 Correct 269 ms 139288 KB Output is correct
15 Correct 275 ms 149200 KB Output is correct
16 Correct 272 ms 162712 KB Output is correct
17 Correct 325 ms 190640 KB Output is correct
18 Correct 436 ms 254056 KB Output is correct
19 Correct 284 ms 167936 KB Output is correct
20 Correct 270 ms 139020 KB Output is correct
21 Correct 315 ms 170360 KB Output is correct
22 Correct 357 ms 202096 KB Output is correct
23 Correct 396 ms 208204 KB Output is correct
24 Correct 383 ms 188176 KB Output is correct
25 Correct 377 ms 188224 KB Output is correct
26 Correct 280 ms 140312 KB Output is correct
27 Correct 371 ms 180200 KB Output is correct
28 Correct 348 ms 178116 KB Output is correct
29 Correct 440 ms 231392 KB Output is correct
30 Correct 350 ms 189380 KB Output is correct
31 Correct 298 ms 166132 KB Output is correct
32 Correct 423 ms 222160 KB Output is correct
33 Correct 330 ms 170380 KB Output is correct
34 Correct 445 ms 233924 KB Output is correct
35 Correct 270 ms 140996 KB Output is correct
36 Correct 280 ms 150980 KB Output is correct
37 Correct 302 ms 166388 KB Output is correct
38 Correct 455 ms 252716 KB Output is correct
39 Correct 332 ms 189892 KB Output is correct
40 Correct 443 ms 254660 KB Output is correct

Subtask #7
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 5 ms 2892 KB Output is correct
3 Correct 5 ms 3148 KB Output is correct
4 Correct 3 ms 1740 KB Output is correct
5 Correct 1 ms 648 KB Output is correct
6 Correct 4 ms 2636 KB Output is correct
7 Correct 5 ms 2764 KB Output is correct
8 Correct 5 ms 3148 KB Output is correct
9 Correct 4 ms 2252 KB Output is correct
10 Correct 5 ms 3020 KB Output is correct
11 Correct 5 ms 3148 KB Output is correct
12 Correct 3 ms 1612 KB Output is correct
13 Correct 384 ms 218692 KB Output is correct
14 Correct 269 ms 139288 KB Output is correct
15 Correct 275 ms 149200 KB Output is correct
16 Correct 272 ms 162712 KB Output is correct
17 Correct 325 ms 190640 KB Output is correct
18 Correct 436 ms 254056 KB Output is correct
19 Correct 284 ms 167936 KB Output is correct
20 Correct 270 ms 139020 KB Output is correct
21 Correct 315 ms 170360 KB Output is correct
22 Correct 357 ms 202096 KB Output is correct
23 Correct 396 ms 208204 KB Output is correct
24 Correct 383 ms 188176 KB Output is correct
25 Correct 377 ms 188224 KB Output is correct
26 Correct 280 ms 140312 KB Output is correct
27 Correct 371 ms 180200 KB Output is correct
28 Correct 348 ms 178116 KB Output is correct
29 Correct 440 ms 231392 KB Output is correct
30 Correct 350 ms 189380 KB Output is correct
31 Correct 298 ms 166132 KB Output is correct
32 Incorrect 366 ms 217076 KB Output isn't correct
33 Halted 0 ms 0 KB -