oj.uz

Submission #1089882

# Submission time Handle Problem Language Result Execution time Memory
1089882 2024-09-17T11:05:24 Z KALARRY Tricks of the Trade (CEOI23_trade) C++14
15 / 100
 1409 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;
        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

trade.cpp: In function 'int main()':
trade.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     scanf("%lld%lld",&N,&K);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
trade.cpp:40:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |         scanf("%lld",&a[i]);
      |         ~~~~~^~~~~~~~~~~~~~
trade.cpp:42:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |         scanf("%lld",&b[i]);
      |         ~~~~~^~~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Partially correct 468 ms 1203840 KB Partially correct
2 Partially correct 466 ms 1203792 KB Partially correct

Subtask #1
5.0 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 460 ms 1203984 KB Partially correct
2 Partially correct 466 ms 1203868 KB Partially correct
3 Partially correct 454 ms 1203816 KB Partially correct
4 Partially correct 425 ms 1204816 KB Partially correct
5 Partially correct 440 ms 1205588 KB Partially correct
6 Partially correct 427 ms 1204140 KB Partially correct
7 Partially correct 432 ms 1204564 KB Partially correct
8 Partially correct 437 ms 1204876 KB Partially correct
9 Partially correct 488 ms 1204564 KB Partially correct
10 Partially correct 478 ms 1204560 KB Partially correct
11 Partially correct 482 ms 1204560 KB Partially correct

Subtask #2
5.0 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 460 ms 1203984 KB Partially correct
2 Partially correct 466 ms 1203868 KB Partially correct
3 Partially correct 454 ms 1203816 KB Partially correct
4 Partially correct 425 ms 1204816 KB Partially correct
5 Partially correct 440 ms 1205588 KB Partially correct
6 Partially correct 427 ms 1204140 KB Partially correct
7 Partially correct 432 ms 1204564 KB Partially correct
8 Partially correct 437 ms 1204876 KB Partially correct
9 Partially correct 488 ms 1204564 KB Partially correct
10 Partially correct 478 ms 1204560 KB Partially correct
11 Partially correct 482 ms 1204560 KB Partially correct
12 Partially correct 468 ms 1203784 KB Partially correct
13 Partially correct 472 ms 1203996 KB Partially correct
14 Partially correct 466 ms 1203792 KB Partially correct
15 Partially correct 471 ms 1204740 KB Partially correct
16 Partially correct 468 ms 1205584 KB Partially correct
17 Partially correct 462 ms 1204316 KB Partially correct
18 Partially correct 471 ms 1204412 KB Partially correct
19 Partially correct 492 ms 1204816 KB Partially correct
20 Partially correct 461 ms 1204560 KB Partially correct
21 Partially correct 459 ms 1204560 KB Partially correct
22 Partially correct 508 ms 1204560 KB Partially correct
23 Partially correct 1409 ms 1550976 KB Partially correct
24 Partially correct 437 ms 1214744 KB Partially correct
25 Partially correct 674 ms 1305940 KB Partially correct
26 Partially correct 458 ms 1233012 KB Partially correct
27 Partially correct 1062 ms 1482876 KB Partially correct
28 Partially correct 481 ms 1213940 KB Partially correct
29 Partially correct 1056 ms 1387092 KB Partially correct

Subtask #3
5.0 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 471 ms 1203852 KB Partially correct
2 Partially correct 688 ms 1676116 KB Partially correct
3 Partially correct 693 ms 1627904 KB Partially correct
4 Partially correct 948 ms 1628056 KB Partially correct
5 Partially correct 699 ms 1653072 KB Partially correct
6 Partially correct 697 ms 1653312 KB Partially correct
7 Partially correct 683 ms 1627120 KB Partially correct
8 Partially correct 674 ms 1627988 KB Partially correct
9 Partially correct 680 ms 1626368 KB Partially correct
10 Partially correct 731 ms 1677252 KB Partially correct

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 471 ms 1203852 KB Partially correct
2 Partially correct 688 ms 1676116 KB Partially correct
3 Partially correct 693 ms 1627904 KB Partially correct
4 Partially correct 948 ms 1628056 KB Partially correct
5 Partially correct 699 ms 1653072 KB Partially correct
6 Partially correct 697 ms 1653312 KB Partially correct
7 Partially correct 683 ms 1627120 KB Partially correct
8 Partially correct 674 ms 1627988 KB Partially correct
9 Partially correct 680 ms 1626368 KB Partially correct
10 Partially correct 731 ms 1677252 KB Partially correct
11 Partially correct 495 ms 1203796 KB Partially correct
12 Partially correct 661 ms 1676540 KB Partially correct
13 Partially correct 617 ms 1627984 KB Partially correct
14 Partially correct 620 ms 1628116 KB Partially correct
15 Partially correct 629 ms 1653072 KB Partially correct
16 Partially correct 717 ms 1653356 KB Partially correct
17 Partially correct 710 ms 1627032 KB Partially correct
18 Partially correct 723 ms 1628132 KB Partially correct
19 Partially correct 669 ms 1626448 KB Partially correct
20 Partially correct 725 ms 1677392 KB Partially correct
21 Partially correct 493 ms 1203960 KB Partially correct
22 Partially correct 494 ms 1203792 KB Partially correct
23 Partially correct 478 ms 1205036 KB Partially correct
24 Partially correct 479 ms 1205576 KB Partially correct
25 Partially correct 497 ms 1204328 KB Partially correct
26 Partially correct 469 ms 1204756 KB Partially correct
27 Partially correct 428 ms 1204688 KB Partially correct
28 Partially correct 434 ms 1204556 KB Partially correct
29 Partially correct 427 ms 1204456 KB Partially correct
30 Partially correct 424 ms 1204564 KB Partially correct
31 Runtime error 1163 ms 2097152 KB Execution killed with signal 9
32 Halted 0 ms 0 KB -

Subtask #5
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Partially correct 468 ms 1203840 KB Partially correct
2 Partially correct 466 ms 1203792 KB Partially correct
3 Partially correct 460 ms 1203984 KB Partially correct
4 Partially correct 466 ms 1203868 KB Partially correct
5 Partially correct 454 ms 1203816 KB Partially correct
6 Partially correct 425 ms 1204816 KB Partially correct
7 Partially correct 440 ms 1205588 KB Partially correct
8 Partially correct 427 ms 1204140 KB Partially correct
9 Partially correct 432 ms 1204564 KB Partially correct
10 Partially correct 437 ms 1204876 KB Partially correct
11 Partially correct 488 ms 1204564 KB Partially correct
12 Partially correct 478 ms 1204560 KB Partially correct
13 Partially correct 482 ms 1204560 KB Partially correct
14 Partially correct 468 ms 1203784 KB Partially correct
15 Partially correct 472 ms 1203996 KB Partially correct
16 Partially correct 466 ms 1203792 KB Partially correct
17 Partially correct 471 ms 1204740 KB Partially correct
18 Partially correct 468 ms 1205584 KB Partially correct
19 Partially correct 462 ms 1204316 KB Partially correct
20 Partially correct 471 ms 1204412 KB Partially correct
21 Partially correct 492 ms 1204816 KB Partially correct
22 Partially correct 461 ms 1204560 KB Partially correct
23 Partially correct 459 ms 1204560 KB Partially correct
24 Partially correct 508 ms 1204560 KB Partially correct
25 Partially correct 1409 ms 1550976 KB Partially correct
26 Partially correct 437 ms 1214744 KB Partially correct
27 Partially correct 674 ms 1305940 KB Partially correct
28 Partially correct 458 ms 1233012 KB Partially correct
29 Partially correct 1062 ms 1482876 KB Partially correct
30 Partially correct 481 ms 1213940 KB Partially correct
31 Partially correct 1056 ms 1387092 KB Partially correct
32 Partially correct 471 ms 1203852 KB Partially correct
33 Partially correct 688 ms 1676116 KB Partially correct
34 Partially correct 693 ms 1627904 KB Partially correct
35 Partially correct 948 ms 1628056 KB Partially correct
36 Partially correct 699 ms 1653072 KB Partially correct
37 Partially correct 697 ms 1653312 KB Partially correct
38 Partially correct 683 ms 1627120 KB Partially correct
39 Partially correct 674 ms 1627988 KB Partially correct
40 Partially correct 680 ms 1626368 KB Partially correct
41 Partially correct 731 ms 1677252 KB Partially correct
42 Partially correct 495 ms 1203796 KB Partially correct
43 Partially correct 661 ms 1676540 KB Partially correct
44 Partially correct 617 ms 1627984 KB Partially correct
45 Partially correct 620 ms 1628116 KB Partially correct
46 Partially correct 629 ms 1653072 KB Partially correct
47 Partially correct 717 ms 1653356 KB Partially correct
48 Partially correct 710 ms 1627032 KB Partially correct
49 Partially correct 723 ms 1628132 KB Partially correct
50 Partially correct 669 ms 1626448 KB Partially correct
51 Partially correct 725 ms 1677392 KB Partially correct
52 Partially correct 493 ms 1203960 KB Partially correct
53 Partially correct 494 ms 1203792 KB Partially correct
54 Partially correct 478 ms 1205036 KB Partially correct
55 Partially correct 479 ms 1205576 KB Partially correct
56 Partially correct 497 ms 1204328 KB Partially correct
57 Partially correct 469 ms 1204756 KB Partially correct
58 Partially correct 428 ms 1204688 KB Partially correct
59 Partially correct 434 ms 1204556 KB Partially correct
60 Partially correct 427 ms 1204456 KB Partially correct
61 Partially correct 424 ms 1204564 KB Partially correct
62 Runtime error 1163 ms 2097152 KB Execution killed with signal 9
63 Halted 0 ms 0 KB -