oj.uz

Submission #869062

# Submission time Handle Problem Language Result Execution time Memory
869062 2023-11-03T04:25:14 Z Darren0724 Coin Collecting (JOI19_ho_t4) C++17
0 / 100
 0 ms 460 KB 
#include<bits/stdc++.h>
using namespace std;
#define LCBorz ios_base::sync_with_stdio(false);cin.tie(0);
#define int long long
#define all(x) x.begin(),x.end()
const int INF=1e18;
const int mod=998244353;


int32_t main(){
    LCBorz;
    int n;cin>>n;
    int m=n*2;
    vector<int> a(m),b(m);
    int ans=0;
    vector<int> dp1(m+1),dp2(m+1);
    for(int i=0;i<m;i++){
        cin>>a[i]>>b[i];
        int place=0;
        if(a[i]>n){
            place=n;
            ans+=a[i]-n;
        }
        else if(a[i]<1){
            place=1;
            ans+=1-a[i];
        }
        else{
            place=a[i];
        }
        if(b[i]<=1){
            ans+=1-b[i];
            dp1[place]++;
        }
        else{
            ans+=b[i]-2;
            dp2[place]++;
        }
    }
    /*for(int i=1;i<=n;i++){
        cout<<dp1[i]<<' ';
    }
    cout<<endl;
    for(int i=1;i<=n;i++){
        cout<<dp2[i]<<' ';
    }
    cout<<endl;
    cout<<ans<<endl;*/
    for(int i=1;i<=n;i++){
        //cout<<dp1[i]<<' '<<dp2[i]<<endl;
        if(dp1[i]+dp2[i]>=2){
            if(dp1[i]==0){
                dp1[i]=1;
                dp2[i]--;
                ans++;
            }
            if(dp2[i]==0){
                dp2[i]=1;
                dp1[i]--;
                ans++;
            }
            dp1[i+1]+=dp1[i]-1;
            dp2[i+1]+=dp2[i]-1;
            ans+=dp1[i]+dp2[i]-2;
            dp1[i]=1;
            dp2[i]=1;
        }
        else{
            if(dp1[i]==0){
                for(int j=i+1;j<=n;j++){
                    if(dp1[j]){
                        dp1[j]--;
                        ans+=j-i;
                        break;
                    }
                    if(dp2[j]){
                        dp2[j]--;
                        ans+=j-i+1;
                        break;
                    }
                }
                dp1[i]=1;
            }
            if(dp2[i]==0){
                for(int j=i+1;j<=n;j++){
                    if(dp2[j]){
                        dp2[j]--;
                        ans+=j-i;
                        break;
                    }
                    if(dp1[j]){
                        dp1[j]--;
                        ans+=j-i+1;
                        break;
                    }
                }
                dp2[i]=1;
            }
            dp1[i+1]+=dp1[i]-1;
            dp2[i+1]+=dp2[i]-1;
            ans+=dp1[i]+dp2[i]-2;
        }
        //cout<<ans<<endl;
    }
    cout<<ans<<endl;
    
    return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 460 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 452 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 460 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 452 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 460 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 452 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -