Submission #519327

#	Time	Username	Problem	Language	Result	Execution time	Memory
519327		azberjibiou	Coin Collecting (JOI19_ho_t4)	C++17	100 / 100	55 ms	7348 KiB

joi2019_ho_t4

#include <bits/stdc++.h>
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fir first
#define sec second
#define pdd pair<double, double>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pmax pair<__int128, __int128>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
typedef long long ll;
using namespace std;
int dx[4]={0, 1, 0, -1}, dy[4]={1, 0, -1 , 0};
const int mxN=100020;
const int mxM=2500000;
const int mxK=105;
const int MOD=1000000007;
const ll INF=1000000000000000001;
int N;
int cntA[mxN][3], cntB[mxN][3];
ll ans;
int main()
{
    gibon
    cin >> N;
    for(int i=0;i<2*N;i++)
    {
        int a, b;
        cin >> a >> b;
        if(a<1) ans+=1-a, a=1;
        if(a>N) ans+=a-N, a=N;
        if(b>2) ans+=b-2, b=2;
        if(b<1) ans+=1-b, b=1;
        cntA[a][b]++;
    }
    for(int i=1;i<=N;i++)   for(int j=1;j<=2;j++)   cntB[i][j]++;
    for(int i=1;i<=N;i++)
    {
        for(int j=1;j<=2;j++)
        {
            int nval=min(cntA[i][j], cntB[i][j]);
            cntA[i][j]-=nval;   cntB[i][j]-=nval;
        }
        for(int j=1;j<=2;j++)
        {
            int nval=min(cntA[i][j], cntB[i][3-j]);
            ans+=nval;
            cntA[i][j]-=nval;   cntB[i][3-j]-=nval;
        }
        for(int j=1;j<=2;j++)   ans+=cntA[i][j]+cntB[i][j];
        for(int j=1;j<=2;j++)   cntA[i+1][j]+=cntA[i][j], cntB[i+1][j]+=cntB[i][j];
    }
    cout << ans;
}

• Subtask 1: 8 / 8
• Subtask 2: 29 / 29
• Subtask 3: 63 / 63