| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1089883 | 2024-09-17T11:07:23 Z | KALARRY | Tricks of the Trade (CEOI23_trade) | C++14 | 1444 ms | 2097152 KB |
//chockolateman
#include<bits/stdc++.h>
using namespace std;
long long N,K,a[250005],b[250005],dp[250005][205];
vector<pair<int,int>> adj[250005][205];
bool visited[250005][205];
bool used[250005];
void dfs(int startv,int startj)
{
queue<pair<int,int>> q;
q.push({startv,startj});
while(!q.empty())
{
int v = q.front().first;
int j = q.front().second;
q.pop();
if(visited[v][j])
return;
visited[v][j] = true;
if(j==0)
return;
for(auto e : adj[v][j])
{
int u = e.first;
int newj = e.second;
if(newj==(j-1))
used[v] = true;
q.push({u,newj});
}
}
}
int main()
{
scanf("%lld%lld",&N,&K);
for(long long i = 1 ; i <= N ; i++)
scanf("%lld",&a[i]);
for(long long i = 1 ; i <= N ; i++)
scanf("%lld",&b[i]);
for(long long j = 1 ; j <= K ; j++)
{
dp[0][j%2] = -1e15;
for(long long i = 1 ; i <= N ; i++)
{
dp[i][j%2] = max(dp[i-1][j%2] - a[i],dp[i-1][(j-1)%2] + b[i] - a[i]);
if(dp[i][j%2]==dp[i-1][j%2] - a[i])
adj[i][j].push_back({i-1,j});
if(dp[i][j%2] == dp[i-1][(j-1)%2] + b[i] - a[i])
adj[i][j].push_back({i-1,j-1});
}
}
long long ans = -1e15;
for(long long i = 1 ; i <= N ; i++)
ans = max(ans,dp[i][K%2]);
for(long long i = 1 ; i <= N ; i++)
if(dp[i][K%2]==ans)
dfs(i,K);
printf("%lld\n",ans);
for(int i = 1 ; i <= N ; i++)
printf("%d",used[i]);
return 0;
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 453 ms | 1204048 KB | Output is correct |
| 2 | Correct | 433 ms | 1203792 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 479 ms | 1203988 KB | Output is correct |
| 2 | Correct | 473 ms | 1203764 KB | Output is correct |
| 3 | Correct | 488 ms | 1203796 KB | Output is correct |
| 4 | Correct | 473 ms | 1204948 KB | Output is correct |
| 5 | Correct | 430 ms | 1205528 KB | Output is correct |
| 6 | Partially correct | 427 ms | 1204308 KB | Partially correct |
| 7 | Partially correct | 429 ms | 1204480 KB | Partially correct |
| 8 | Partially correct | 451 ms | 1204716 KB | Partially correct |
| 9 | Partially correct | 434 ms | 1204560 KB | Partially correct |
| 10 | Correct | 439 ms | 1204404 KB | Output is correct |
| 11 | Partially correct | 488 ms | 1204380 KB | Partially correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 479 ms | 1203988 KB | Output is correct |
| 2 | Correct | 473 ms | 1203764 KB | Output is correct |
| 3 | Correct | 488 ms | 1203796 KB | Output is correct |
| 4 | Correct | 473 ms | 1204948 KB | Output is correct |
| 5 | Correct | 430 ms | 1205528 KB | Output is correct |
| 6 | Partially correct | 427 ms | 1204308 KB | Partially correct |
| 7 | Partially correct | 429 ms | 1204480 KB | Partially correct |
| 8 | Partially correct | 451 ms | 1204716 KB | Partially correct |
| 9 | Partially correct | 434 ms | 1204560 KB | Partially correct |
| 10 | Correct | 439 ms | 1204404 KB | Output is correct |
| 11 | Partially correct | 488 ms | 1204380 KB | Partially correct |
| 12 | Correct | 465 ms | 1203792 KB | Output is correct |
| 13 | Correct | 456 ms | 1204012 KB | Output is correct |
| 14 | Correct | 461 ms | 1203792 KB | Output is correct |
| 15 | Correct | 431 ms | 1204828 KB | Output is correct |
| 16 | Correct | 432 ms | 1205520 KB | Output is correct |
| 17 | Partially correct | 428 ms | 1204304 KB | Partially correct |
| 18 | Partially correct | 427 ms | 1204528 KB | Partially correct |
| 19 | Partially correct | 430 ms | 1204648 KB | Partially correct |
| 20 | Partially correct | 430 ms | 1204568 KB | Partially correct |
| 21 | Correct | 458 ms | 1204816 KB | Output is correct |
| 22 | Partially correct | 469 ms | 1204560 KB | Partially correct |
| 23 | Partially correct | 1444 ms | 1551036 KB | Partially correct |
| 24 | Partially correct | 467 ms | 1214924 KB | Partially correct |
| 25 | Partially correct | 699 ms | 1305936 KB | Partially correct |
| 26 | Partially correct | 490 ms | 1233232 KB | Partially correct |
| 27 | Partially correct | 1012 ms | 1482580 KB | Partially correct |
| 28 | Correct | 458 ms | 1214032 KB | Output is correct |
| 29 | Partially correct | 1024 ms | 1387092 KB | Partially correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 489 ms | 1203792 KB | Output is correct |
| 2 | Correct | 713 ms | 1676272 KB | Output is correct |
| 3 | Correct | 602 ms | 1628076 KB | Output is correct |
| 4 | Correct | 616 ms | 1627960 KB | Output is correct |
| 5 | Partially correct | 655 ms | 1653328 KB | Partially correct |
| 6 | Partially correct | 637 ms | 1653328 KB | Partially correct |
| 7 | Partially correct | 620 ms | 1626964 KB | Partially correct |
| 8 | Correct | 650 ms | 1627984 KB | Output is correct |
| 9 | Correct | 659 ms | 1626352 KB | Output is correct |
| 10 | Correct | 685 ms | 1677496 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 489 ms | 1203792 KB | Output is correct |
| 2 | Correct | 713 ms | 1676272 KB | Output is correct |
| 3 | Correct | 602 ms | 1628076 KB | Output is correct |
| 4 | Correct | 616 ms | 1627960 KB | Output is correct |
| 5 | Partially correct | 655 ms | 1653328 KB | Partially correct |
| 6 | Partially correct | 637 ms | 1653328 KB | Partially correct |
| 7 | Partially correct | 620 ms | 1626964 KB | Partially correct |
| 8 | Correct | 650 ms | 1627984 KB | Output is correct |
| 9 | Correct | 659 ms | 1626352 KB | Output is correct |
| 10 | Correct | 685 ms | 1677496 KB | Output is correct |
| 11 | Correct | 427 ms | 1203796 KB | Output is correct |
| 12 | Correct | 657 ms | 1676104 KB | Output is correct |
| 13 | Correct | 627 ms | 1627984 KB | Output is correct |
| 14 | Correct | 626 ms | 1627984 KB | Output is correct |
| 15 | Partially correct | 692 ms | 1652948 KB | Partially correct |
| 16 | Partially correct | 714 ms | 1653352 KB | Partially correct |
| 17 | Partially correct | 670 ms | 1627068 KB | Partially correct |
| 18 | Correct | 610 ms | 1627800 KB | Output is correct |
| 19 | Correct | 606 ms | 1626324 KB | Output is correct |
| 20 | Correct | 906 ms | 1677392 KB | Output is correct |
| 21 | Correct | 434 ms | 1204048 KB | Output is correct |
| 22 | Correct | 434 ms | 1203796 KB | Output is correct |
| 23 | Correct | 490 ms | 1204924 KB | Output is correct |
| 24 | Correct | 469 ms | 1205584 KB | Output is correct |
| 25 | Partially correct | 469 ms | 1204268 KB | Partially correct |
| 26 | Partially correct | 448 ms | 1204660 KB | Partially correct |
| 27 | Partially correct | 433 ms | 1204744 KB | Partially correct |
| 28 | Partially correct | 435 ms | 1204604 KB | Partially correct |
| 29 | Correct | 436 ms | 1204564 KB | Output is correct |
| 30 | Partially correct | 429 ms | 1204560 KB | Partially correct |
| 31 | Runtime error | 1099 ms | 2097152 KB | Execution killed with signal 9 |
| 32 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 453 ms | 1204048 KB | Output is correct |
| 2 | Correct | 433 ms | 1203792 KB | Output is correct |
| 3 | Correct | 479 ms | 1203988 KB | Output is correct |
| 4 | Correct | 473 ms | 1203764 KB | Output is correct |
| 5 | Correct | 488 ms | 1203796 KB | Output is correct |
| 6 | Correct | 473 ms | 1204948 KB | Output is correct |
| 7 | Correct | 430 ms | 1205528 KB | Output is correct |
| 8 | Partially correct | 427 ms | 1204308 KB | Partially correct |
| 9 | Partially correct | 429 ms | 1204480 KB | Partially correct |
| 10 | Partially correct | 451 ms | 1204716 KB | Partially correct |
| 11 | Partially correct | 434 ms | 1204560 KB | Partially correct |
| 12 | Correct | 439 ms | 1204404 KB | Output is correct |
| 13 | Partially correct | 488 ms | 1204380 KB | Partially correct |
| 14 | Correct | 465 ms | 1203792 KB | Output is correct |
| 15 | Correct | 456 ms | 1204012 KB | Output is correct |
| 16 | Correct | 461 ms | 1203792 KB | Output is correct |
| 17 | Correct | 431 ms | 1204828 KB | Output is correct |
| 18 | Correct | 432 ms | 1205520 KB | Output is correct |
| 19 | Partially correct | 428 ms | 1204304 KB | Partially correct |
| 20 | Partially correct | 427 ms | 1204528 KB | Partially correct |
| 21 | Partially correct | 430 ms | 1204648 KB | Partially correct |
| 22 | Partially correct | 430 ms | 1204568 KB | Partially correct |
| 23 | Correct | 458 ms | 1204816 KB | Output is correct |
| 24 | Partially correct | 469 ms | 1204560 KB | Partially correct |
| 25 | Partially correct | 1444 ms | 1551036 KB | Partially correct |
| 26 | Partially correct | 467 ms | 1214924 KB | Partially correct |
| 27 | Partially correct | 699 ms | 1305936 KB | Partially correct |
| 28 | Partially correct | 490 ms | 1233232 KB | Partially correct |
| 29 | Partially correct | 1012 ms | 1482580 KB | Partially correct |
| 30 | Correct | 458 ms | 1214032 KB | Output is correct |
| 31 | Partially correct | 1024 ms | 1387092 KB | Partially correct |
| 32 | Correct | 489 ms | 1203792 KB | Output is correct |
| 33 | Correct | 713 ms | 1676272 KB | Output is correct |
| 34 | Correct | 602 ms | 1628076 KB | Output is correct |
| 35 | Correct | 616 ms | 1627960 KB | Output is correct |
| 36 | Partially correct | 655 ms | 1653328 KB | Partially correct |
| 37 | Partially correct | 637 ms | 1653328 KB | Partially correct |
| 38 | Partially correct | 620 ms | 1626964 KB | Partially correct |
| 39 | Correct | 650 ms | 1627984 KB | Output is correct |
| 40 | Correct | 659 ms | 1626352 KB | Output is correct |
| 41 | Correct | 685 ms | 1677496 KB | Output is correct |
| 42 | Correct | 427 ms | 1203796 KB | Output is correct |
| 43 | Correct | 657 ms | 1676104 KB | Output is correct |
| 44 | Correct | 627 ms | 1627984 KB | Output is correct |
| 45 | Correct | 626 ms | 1627984 KB | Output is correct |
| 46 | Partially correct | 692 ms | 1652948 KB | Partially correct |
| 47 | Partially correct | 714 ms | 1653352 KB | Partially correct |
| 48 | Partially correct | 670 ms | 1627068 KB | Partially correct |
| 49 | Correct | 610 ms | 1627800 KB | Output is correct |
| 50 | Correct | 606 ms | 1626324 KB | Output is correct |
| 51 | Correct | 906 ms | 1677392 KB | Output is correct |
| 52 | Correct | 434 ms | 1204048 KB | Output is correct |
| 53 | Correct | 434 ms | 1203796 KB | Output is correct |
| 54 | Correct | 490 ms | 1204924 KB | Output is correct |
| 55 | Correct | 469 ms | 1205584 KB | Output is correct |
| 56 | Partially correct | 469 ms | 1204268 KB | Partially correct |
| 57 | Partially correct | 448 ms | 1204660 KB | Partially correct |
| 58 | Partially correct | 433 ms | 1204744 KB | Partially correct |
| 59 | Partially correct | 435 ms | 1204604 KB | Partially correct |
| 60 | Correct | 436 ms | 1204564 KB | Output is correct |
| 61 | Partially correct | 429 ms | 1204560 KB | Partially correct |
| 62 | Runtime error | 1099 ms | 2097152 KB | Execution killed with signal 9 |
| 63 | Halted | 0 ms | 0 KB | - |