제출 #1330220

#제출 시각아이디문제언어결과실행 시간메모리
1330220bradley0927Grid Coloring (JOI25_ho_t1)C++20
0 / 100
512 ms1114112 KiB
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> mp(2 * n);
    vector<vector<int> > grid(n, vector<int>(n)); //grid is mapped
    for (int i = 0; i < n; i++) {
        cin >> grid[i][0];
        mp[i] = grid[i][0];
    }
    for (int i = 0; i < n; i++) {
        cin >> grid[0][i];
        mp[i+n] = grid[0][i];
    }
    sort(mp.begin(), mp.end());
    mp.erase(unique(mp.begin(), mp.end()), mp.end());
    vector<int> count(mp.size(), 0);
    int max_cnt = 0, max_idx = 0;
    for (int i = 0; i < n; i++) {
        grid[i][0] = lower_bound(mp.begin(), mp.end(), grid[i][0]) - mp.begin();
        grid[0][i] = lower_bound(mp.begin(), mp.end(), grid[0][i]) - mp.begin();
        count[grid[i][0]]++;
        count[grid[0][i]]++;
    }
    count[grid[0][0]]--; //avoid double counting
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < n; j++) {
            grid[i][j] = max(grid[i - 1][j], grid[i][j - 1]);
            count[grid[i][j]]++;
            if (count[grid[i][j]] > max_cnt) {
                max_cnt = count[grid[i][j]];
                max_idx = grid[i][j];
            } else if (count[grid[i][j]] == max_cnt) {
                max_idx = max(max_idx, grid[i][j]); //choose color with larger index
            }
        }
    }

    cout << mp[max_idx] << " " << max_cnt << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...