제출 #677652

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
677652		Cross_Ratio	송금 (JOI19_remittance)	C++14	55 / 100	1026 ms	51412 KiB

remittance

#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> P;
int A[1000005];
int B[1000005];
signed main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int N;
    cin >> N;
    int i, j;
    for(i=0;i<N;i++) cin >> A[i] >> B[i];
    priority_queue<P> PQ;
    for(i=0;i<N;i++) {
        if(A[i] > B[i]+1) {
            PQ.push(P(A[i] - B[i], i));
        }
    }
    while(!PQ.empty()) {
        P k = PQ.top();
        PQ.pop();
        int id = k.second;
        if(A[id] <= B[id]+1) continue;
        int v = A[id] - B[id];
        v /= 2;
        A[id] -= v*2;
        A[(id+1)%N] += v;
        if(A[(id+1)%N]>B[(id+1)%N]+1) {
            PQ.push(P(A[(id+1)%N]-B[(id+1)%N], (id+1)%N));
        }
    }
    bool isPos1 = true;
    bool isPos2 = false;
    for(i=0;i<N;i++) {
        if(A[i]>=2) isPos2 = true;
    }
    for(i=0;i<N;i++) {
        if(A[i]!=B[i]) isPos1 = false;
        if(A[i]!=B[i]+1) isPos2 = false;
        assert(A[i]<B[i]+2);
    }
    
    cout << (isPos1||isPos2?"Yes":"No");
}

컴파일 시 표준 에러 (stderr) 메시지

remittance.cpp: In function 'int main()':
remittance.cpp:13:12: warning: unused variable 'j' [-Wunused-variable]
   13 |     int i, j;
      |            ^

• Subtask 1: 15 / 15
• Subtask 2: 40 / 40
• Subtask 3: 0 / 45