제출 #110414

#제출 시각아이디문제언어결과실행 시간메모리
110414Leonardo_PaesCoin Collecting (JOI19_ho_t4)C++11
100 / 100
238 ms3576 KiB
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5+10;

int n, mat[maxn][3];

long long ans=0;

void solve() {
    long long num1=0, num2=0;
    for (long long i=1; i<=n; i++) {
        num1 += (mat[i][1]-1);
        num2 += (mat[i][2]-1);
        // caso de na primeira linha ter coins estacadas e na segunda ter mais espaços em branco do que moeadas
        while(num1>0 and num2<0) {
            num1--;
            num2++;
            ans++;
        }
        // caso de na segund linha ter coins estacadas e na primeira ter mais espaços em branco do que moedas
        while(num1<0 and num2>0) {
            num1++;
            num2--;
            ans++;
        }
        // somo as distancias percorridas a partir das posicoes nao ocupadas
        // quando um dos nums zera, não há posicoes precisando de moedas atualmente
        ans+=abs(num1)+abs(num2);
    }
}

int main(){
    cin >> n;

    for(int i=1; i<=2*n; i++){
        int x, y;

        cin >> x >> y;

        if(x<1){
            if(y>=2){
                mat[1][2]++;
                ans+=abs(x-1)+abs(y-2);
            }
            else{
                mat[1][1]++;
                ans+=abs(x-1)+abs(y-1);
            }
        }
        if(x>=1 and x<=n){
            if(y>=2){
                ans+=abs(y-2);
                mat[x][2]++;
            }
            else{
                ans+=abs(y-1);
                mat[x][1]++;
            }
        }
        if(x>n){
            if(y>=2){
                mat[n][2]++;
                ans+=abs(x-n)+abs(y-2);
            }
            else{
                mat[n][1]++;
                ans+=abs(x-n)+abs(y-1);
            }
        }
    }
    solve();
    cout << ans << endl;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...