oj.uz

Submission #1072258

# Submission time Handle Problem Language Result Execution time Memory
1072258 2024-08-23T16:05:53 Z edogawa_something Tricks of the Trade (CEOI23_trade) C++17
20 / 100
 372 ms 598740 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vii;
typedef pair<ll,ll> pii;
#define F first
#define S second
#define all(v) v.begin(),v.end()
#define pb push_back
const ll M=5e5+10;
const ll inf=2e18;
ll ma[301],dp[M][301],n,k,a[M],b[M],suf[M];
int main() {
    ios_base::sync_with_stdio(0),cin.tie(0);
    cin>>n>>k;
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0;i<n;i++)
        cin>>b[i];
    ll sum=0;
    suf[n]=0;
    for(int i=n-1;i>=0;i--) {
        sum-=a[i];
        dp[i][0]=sum;
        for(int j=1;j<=k;j++)
        dp[i][j]=-inf;
    }
    for(int i=n-1;i>=0;i--)
        suf[i]=suf[i+1]+a[i];
    sum=0;
    for(int i=0;i<=k;i++)
        ma[i]=-inf;
    ma[0]=-suf[0];
    for(int i=0;i<n;i++) {
        ma[0]=max(ma[0],dp[i][0]);
        for(int j=k;j>=1;j--) {
            dp[i][j]=max(dp[i][j],ma[j-1]+b[i]);
            ma[j]=max(ma[j],dp[i][j]);
        }
    }
    ll ans=-inf;
    for(int i=0;i<n;i++)
        ans=max(ans,dp[i][k]+suf[i+1]);
    cout<<ans<<'\n';
    for(int i=0;i<n;i++)
        cout<<0;
    return 0;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 344 KB Partially correct
2 Partially correct 1 ms 348 KB Partially correct

Subtask #1
5.0 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 344 KB Partially correct
2 Partially correct 1 ms 348 KB Partially correct
3 Partially correct 1 ms 348 KB Partially correct
4 Partially correct 0 ms 860 KB Partially correct
5 Partially correct 1 ms 860 KB Partially correct
6 Partially correct 0 ms 860 KB Partially correct
7 Partially correct 1 ms 860 KB Partially correct
8 Partially correct 1 ms 856 KB Partially correct
9 Partially correct 1 ms 860 KB Partially correct
10 Partially correct 1 ms 860 KB Partially correct
11 Partially correct 1 ms 860 KB Partially correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 344 KB Partially correct
2 Partially correct 1 ms 348 KB Partially correct
3 Partially correct 1 ms 348 KB Partially correct
4 Partially correct 0 ms 860 KB Partially correct
5 Partially correct 1 ms 860 KB Partially correct
6 Partially correct 0 ms 860 KB Partially correct
7 Partially correct 1 ms 860 KB Partially correct
8 Partially correct 1 ms 856 KB Partially correct
9 Partially correct 1 ms 860 KB Partially correct
10 Partially correct 1 ms 860 KB Partially correct
11 Partially correct 1 ms 860 KB Partially correct
12 Partially correct 0 ms 344 KB Partially correct
13 Partially correct 1 ms 344 KB Partially correct
14 Partially correct 0 ms 348 KB Partially correct
15 Partially correct 1 ms 860 KB Partially correct
16 Partially correct 1 ms 860 KB Partially correct
17 Partially correct 1 ms 860 KB Partially correct
18 Partially correct 1 ms 860 KB Partially correct
19 Partially correct 1 ms 860 KB Partially correct
20 Partially correct 1 ms 860 KB Partially correct
21 Partially correct 1 ms 860 KB Partially correct
22 Partially correct 1 ms 856 KB Partially correct
23 Runtime error 73 ms 29476 KB Execution killed with signal 11
24 Halted 0 ms 0 KB -

Subtask #3
5.0 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 344 KB Partially correct
2 Partially correct 240 ms 596328 KB Partially correct
3 Partially correct 241 ms 598612 KB Partially correct
4 Partially correct 239 ms 598500 KB Partially correct
5 Partially correct 213 ms 598508 KB Partially correct
6 Partially correct 231 ms 598052 KB Partially correct
7 Partially correct 209 ms 597744 KB Partially correct
8 Partially correct 215 ms 598608 KB Partially correct
9 Partially correct 209 ms 597072 KB Partially correct
10 Partially correct 209 ms 597588 KB Partially correct

Subtask #4
10.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 344 KB Partially correct
2 Partially correct 240 ms 596328 KB Partially correct
3 Partially correct 241 ms 598612 KB Partially correct
4 Partially correct 239 ms 598500 KB Partially correct
5 Partially correct 213 ms 598508 KB Partially correct
6 Partially correct 231 ms 598052 KB Partially correct
7 Partially correct 209 ms 597744 KB Partially correct
8 Partially correct 215 ms 598608 KB Partially correct
9 Partially correct 209 ms 597072 KB Partially correct
10 Partially correct 209 ms 597588 KB Partially correct
11 Partially correct 1 ms 348 KB Partially correct
12 Partially correct 202 ms 596536 KB Partially correct
13 Partially correct 216 ms 598740 KB Partially correct
14 Partially correct 236 ms 598696 KB Partially correct
15 Partially correct 218 ms 598352 KB Partially correct
16 Partially correct 228 ms 598096 KB Partially correct
17 Partially correct 221 ms 597588 KB Partially correct
18 Partially correct 230 ms 598480 KB Partially correct
19 Partially correct 224 ms 596972 KB Partially correct
20 Partially correct 229 ms 597596 KB Partially correct
21 Partially correct 1 ms 348 KB Partially correct
22 Partially correct 0 ms 344 KB Partially correct
23 Partially correct 0 ms 860 KB Partially correct
24 Partially correct 0 ms 860 KB Partially correct
25 Partially correct 1 ms 856 KB Partially correct
26 Partially correct 1 ms 860 KB Partially correct
27 Partially correct 1 ms 856 KB Partially correct
28 Partially correct 1 ms 860 KB Partially correct
29 Partially correct 1 ms 860 KB Partially correct
30 Partially correct 1 ms 856 KB Partially correct
31 Partially correct 372 ms 598652 KB Partially correct
32 Partially correct 219 ms 598504 KB Partially correct
33 Partially correct 347 ms 598128 KB Partially correct
34 Partially correct 329 ms 597884 KB Partially correct
35 Partially correct 327 ms 597844 KB Partially correct
36 Partially correct 358 ms 596880 KB Partially correct
37 Partially correct 319 ms 596380 KB Partially correct

Subtask #5
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 344 KB Partially correct
2 Partially correct 1 ms 348 KB Partially correct
3 Partially correct 0 ms 344 KB Partially correct
4 Partially correct 1 ms 348 KB Partially correct
5 Partially correct 1 ms 348 KB Partially correct
6 Partially correct 0 ms 860 KB Partially correct
7 Partially correct 1 ms 860 KB Partially correct
8 Partially correct 0 ms 860 KB Partially correct
9 Partially correct 1 ms 860 KB Partially correct
10 Partially correct 1 ms 856 KB Partially correct
11 Partially correct 1 ms 860 KB Partially correct
12 Partially correct 1 ms 860 KB Partially correct
13 Partially correct 1 ms 860 KB Partially correct
14 Partially correct 0 ms 344 KB Partially correct
15 Partially correct 1 ms 344 KB Partially correct
16 Partially correct 0 ms 348 KB Partially correct
17 Partially correct 1 ms 860 KB Partially correct
18 Partially correct 1 ms 860 KB Partially correct
19 Partially correct 1 ms 860 KB Partially correct
20 Partially correct 1 ms 860 KB Partially correct
21 Partially correct 1 ms 860 KB Partially correct
22 Partially correct 1 ms 860 KB Partially correct
23 Partially correct 1 ms 860 KB Partially correct
24 Partially correct 1 ms 856 KB Partially correct
25 Runtime error 73 ms 29476 KB Execution killed with signal 11
26 Halted 0 ms 0 KB -