oj.uz

Submission #674900

# Submission time Handle Problem Language Result Execution time Memory
674900 2022-12-26T13:46:11 Z Ahmed57 Vođe (COCI17_vode) C++14
120 / 120
 985 ms 195528 KB 
#include <bits/stdc++.h>

using namespace std;
deque<pair<int,int>>dq[2][5001];
void addmi(int val,int idx,int z){
    while(!dq[0][z].empty()&&dq[0][z].back().first>=val){
        dq[0][z].pop_back();
    }
    dq[0][z].push_back({val,idx});
}
void delmi(int idx,int z){
    if(!dq[0][z].empty()&&dq[0][z].front().second==idx)dq[0][z].pop_front();
}
void addma(int val,int idx,int z){
    while(!dq[1][z].empty()&&dq[1][z].back().first<=val){
        dq[1][z].pop_back();
    }
    dq[1][z].push_back({val,idx});
}
void delma(int idx,int z){
    if(!dq[1][z].empty()&&dq[1][z].front().second==idx)dq[1][z].pop_front();
}
int main() {
    long long n,m,k;
    cin>>n>>m>>k;
    int arr[n];
    for(int i = 0;i<n;i++){
        cin>>arr[i];
    }
    long long dp[m+1][n+1];
    for(int i = m;i>=0;i--){
        for(int j = 0;j<n;j++){
            if(i==m){
                dp[i][j] = !arr[((j-1)%n+n)%n];
                continue;
            }
            int nex = (j+1)%n;
            if(arr[j]==0){
                dp[i][j] = dq[0][nex].front().first;
            }else{
                dp[i][j] = dq[1][nex].front().first;
            }
        }
        for(int j = 0;j<n;j++){
            if(i+k<=m){
                delmi(i+k,j);
                delma(i+k,j);
            }
            addmi(dp[i][j],i,j);
            addma(dp[i][j],i,j);
        }
    }
    for(int i = 0;i<n;i++){
        cout<<dp[0][i]<<" ";
    }
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6996 KB Output is correct
2 Correct 5 ms 7080 KB Output is correct
3 Correct 5 ms 6996 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7636 KB Output is correct
2 Correct 6 ms 7168 KB Output is correct
3 Correct 8 ms 7548 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7508 KB Output is correct
2 Correct 7 ms 7424 KB Output is correct
3 Correct 6 ms 7552 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7936 KB Output is correct
2 Correct 9 ms 8020 KB Output is correct
3 Correct 8 ms 8020 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 8716 KB Output is correct
2 Correct 11 ms 8532 KB Output is correct
3 Correct 10 ms 8316 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 8440 KB Output is correct
2 Correct 12 ms 8624 KB Output is correct
3 Correct 4 ms 6996 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 30204 KB Output is correct
2 Correct 145 ms 33244 KB Output is correct
3 Correct 859 ms 178608 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 62952 KB Output is correct
2 Correct 848 ms 160364 KB Output is correct
3 Correct 304 ms 66124 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 934 ms 195528 KB Output is correct
2 Correct 23 ms 11312 KB Output is correct
3 Correct 15 ms 9572 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 950 ms 194100 KB Output is correct
2 Correct 889 ms 173784 KB Output is correct
3 Correct 985 ms 192496 KB Output is correct