oj.uz

Submission #1112175

# Submission time Handle Problem Language Result Execution time Memory
1112175 2024-11-13T18:18:36 Z PagodePaiva Fortune Telling 2 (JOI14_fortune_telling2) C++17
4 / 100
 3000 ms 2440 KB 
#include<bits/stdc++.h>

using namespace std;

const int N = 40010;
int dp[N][2];

int main(){
    int n, k;
    cin >> n >> k;
    vector <pair <long long,long long>> v;
    for(int i = 1;i <= n;i++){
        long long a, b;
        cin >> a >> b;
        v.push_back({a, b});
    }
    vector <long long> qr;
    for(int i = 1;i <= k;i++){
        long long x;
        cin >> x;
        qr.push_back(x);
    }
    long long res = 0;
    for(int i = 1;i <= n;i++){
        dp[k][0] = dp[k][1] = 0;
        for(int j = k-1;j >= 0;j--){
            dp[j][0] = (min(v[i-1].first, v[i-1].second) <= qr[j] ? dp[j+1][1]+1 : dp[j+1][0]);
            dp[j][1] = (max(v[i-1].first, v[i-1].second) <= qr[j] ? dp[j+1][0]+1 : dp[j+1][1]);
        }
        int a = v[i-1].first, b = v[i-1].second;
        if(a == min(a, b)){
            if(dp[0][0] % 2 == 0){
                res += a;
            }
            else{
                res += b;
            }
        }
        else{
            if(dp[0][1]%2 == 0){
                res += a;
            }
            else{
                res += b;
            }
        }
        //cout << dp[0][0]<< ' ' << dp[0][1] << '\n';
    }
    cout << res << '\n';
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 336 KB Output is correct
2 Correct 3 ms 336 KB Output is correct
3 Correct 5 ms 336 KB Output is correct
4 Correct 5 ms 336 KB Output is correct
5 Correct 5 ms 496 KB Output is correct
6 Correct 5 ms 336 KB Output is correct
7 Correct 4 ms 520 KB Output is correct
8 Correct 4 ms 336 KB Output is correct
9 Correct 3 ms 336 KB Output is correct
10 Correct 4 ms 336 KB Output is correct
11 Correct 4 ms 336 KB Output is correct
12 Correct 4 ms 336 KB Output is correct
13 Correct 4 ms 336 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 336 KB Output is correct
2 Correct 3 ms 336 KB Output is correct
3 Correct 5 ms 336 KB Output is correct
4 Correct 5 ms 336 KB Output is correct
5 Correct 5 ms 496 KB Output is correct
6 Correct 5 ms 336 KB Output is correct
7 Correct 4 ms 520 KB Output is correct
8 Correct 4 ms 336 KB Output is correct
9 Correct 3 ms 336 KB Output is correct
10 Correct 4 ms 336 KB Output is correct
11 Correct 4 ms 336 KB Output is correct
12 Correct 4 ms 336 KB Output is correct
13 Correct 4 ms 336 KB Output is correct
14 Correct 417 ms 1104 KB Output is correct
15 Correct 1670 ms 1900 KB Output is correct
16 Execution timed out 3068 ms 2440 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 336 KB Output is correct
2 Correct 3 ms 336 KB Output is correct
3 Correct 5 ms 336 KB Output is correct
4 Correct 5 ms 336 KB Output is correct
5 Correct 5 ms 496 KB Output is correct
6 Correct 5 ms 336 KB Output is correct
7 Correct 4 ms 520 KB Output is correct
8 Correct 4 ms 336 KB Output is correct
9 Correct 3 ms 336 KB Output is correct
10 Correct 4 ms 336 KB Output is correct
11 Correct 4 ms 336 KB Output is correct
12 Correct 4 ms 336 KB Output is correct
13 Correct 4 ms 336 KB Output is correct
14 Correct 417 ms 1104 KB Output is correct
15 Correct 1670 ms 1900 KB Output is correct
16 Execution timed out 3068 ms 2440 KB Time limit exceeded
17 Halted 0 ms 0 KB -