Submission #1318889

#	Time	Username	Problem	Language	Result	Execution time	Memory
1318889		nekolie	Adriatic (CEOI13_adriatic)	C++20	100 / 100	444 ms	249700 KiB

adriatic

#include <bits/stdc++.h>
using namespace std;

const int M = 2505, inf = (1<<30);
int n, wp[100*M][2], ile1[M][M], ile2[M][M], mio[M][M][2], rio[M][M][2]; // pionowo, poziomo
long long dp[M][M][2];
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    for (int i = 0; i < M; i++)
        for (int j = 0; j < M; j++)
            mio[i][j][0] = mio[i][j][1] = inf, rio[i][j][0] = rio[i][j][1] = -inf;
    int n; cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> wp[i][0] >> wp[i][1];
        ile1[wp[i][0]][wp[i][1]]++, ile2[wp[i][0]][wp[i][1]]++;
        mio[wp[i][0]][wp[i][1]][0] = rio[wp[i][0]][wp[i][1]][0] = wp[i][0];
        mio[wp[i][0]][wp[i][1]][1] = rio[wp[i][0]][wp[i][1]][1] = wp[i][1];
    }
    for (int i = 1; i <= M-5; i++)
        for (int j = 1; j <= M-5; j++)
            mio[i][j][0] = min({mio[i][j][0],mio[i-1][j][0],mio[i][j-1][0]}), mio[i][j][1] = min({mio[i][j][1],mio[i-1][j][1],mio[i][j-1][1]});
    for (int i = M-5; i > 0; i--)
        for (int j = M-5; j > 0; j--)
            rio[i][j][0] = max({rio[i][j][0],rio[i+1][j][0],rio[i][j+1][0]}), rio[i][j][1] = max({rio[i][j][1],rio[i+1][j][1],rio[i][j+1][1]});
    for (int i = 1; i <= M-5; i++) {
        for (int j = M-5; j > 0; j--) {
            ile1[i][j] += ile1[i-1][j]+ile1[i][j+1]-ile1[i-1][j+1];
            int x = min(mio[i][j-1][0],i), y = max(rio[i+1][j][1],j);
            if (ile1[i][j] > 0)
                dp[i][j][0] = ile1[i][j]+dp[x][y][0];
        }
    }
    for (int i = M-5; i > 0; i--) {
        for (int j = 1; j <= M-5; j++) {
            ile2[i][j] += ile2[i+1][j]+ile2[i][j-1]-ile2[i+1][j-1];
            int x = max(rio[i][j+1][0],i), y = min(mio[i-1][j][1],j);
            if (ile2[i][j] > 0)
                dp[i][j][1] = ile2[i][j]+dp[x][y][1];
        }
    }
    for (int i = 0; i < n; i++)
        cout << n + dp[wp[i][0]][wp[i][1]][0] + dp[wp[i][0]][wp[i][1]][1] - 3 << endl;
    return 0;
}

• Subtask 1: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20