제출 #1281356

#제출 시각아이디문제언어결과실행 시간메모리
1281356cheskaTopical (NOI23_topical)C++20
12 / 100
1099 ms109876 KiB
//dominater orz
//evenvalue orz
//roumak orz
//melody orz
//cpp orz
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define ppii pair<pii, pii> 
#define tiii tuple<int, int, int>
#define g0 get<0>
#define g1 get<1>
#define g2 get<2>
#define f first
#define s second
#define pb push_back
const int N = 2750132;
const int MOD = 1e9+7;
struct module {
    vector<int> r, u;
    module(int k) {
        r.resize(k);
        u.resize(k);
    }
};
bool comp(module a, module b) {
    return (a.r < b.r);
}
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, k; cin >> n >> k;
    vector<module> a(n, module(k));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < k; j++) cin >> a[i].r[j];
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < k; j++) cin >> a[i].u[j];
    }
    sort(a.begin(), a.end(), comp);
    vector<vector<int>> ps(n, vector<int>(k));
    ps[0] = a[0].u;
    for (int i = 1; i < n; i++) {
        ps[i] = ps[i-1];
        for (int j = 0; j < k; j++) {
            ps[i][j] += a[i].u[j];
        }
    }
    int i = -1;
    vector<int> temp(k, 0);
    while (i < n-1 && a[i+1].r == temp) {
        i++;
    }
    if (i == -1) {
        cout << 0;
        return 0;
    }
    vector<int> cr = ps[i];
    int j = k+1;
    while (true) {
        module m(k);
        m.r = cr;
        j = upper_bound(a.begin(), a.end(), m, comp)-a.begin(); j--;
        if (i == j) break;
        i = j;
        cr = ps[j];
    }
    cout << i+1;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...