제출 #1339097

#제출 시각아이디문제언어결과실행 시간메모리
1339097vjudge1Sails (IOI07_sails)C++20
15 / 100
1097 ms131072 KiB
#include <bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define debug(x) cout<<#x<<" = "<<(x)<<"\n";
using namespace std;

void print(vector<vector<int>>& boat) {
        cout<<"elements in boat\n";
        for (int i = 1; i <= 5; ++i) {
            for (int j = 1; j <= 6; ++j) {
                if (boat[i][j]==-1) cout<<7<<' ';
                else cout<<boat[i][j]<<' ';
            } cout<<"line "<<5 - i + 1<<'\n';
        }
}

void print2(vector<pair<int, int>>& v) {
        cout<<"elements in pairs v\n"; 
        for (auto &[a,b] : v) 
        { 
            cout<<a<<' '<<b<<' '<<" | ";
        } cout<<"\n";
}

bool customsort(pair<int, int>& p1, pair<int, int>& p2) {
    if (p1.F != p2.F) return p1.F < p2.F;
    return p1.S > p2.S;
}

int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n; cin>>n;
    vector<pair<int, int>> v(n + 1);
    int mx = 1;
    for (int i = 1; i <= n; ++i) {
        int h, k; cin>>h>>k;
        v[i] = {h, k};
        mx = max(mx, h);
    }
    vector<vector<int>> boat(mx + 1, vector<int>(n + 2, -1));
    int tnf = 0;
    for (int p = n; p >= 1; --p) {
        int pl = n - p + 1;
        //debug(pl);
        vector<pair<int, int>> s;
        for (int h = v[p].F; h >= 1; --h) {
            int nh = mx - h + 1;
            s.PB({boat[nh][pl - 1], h});
            //debug(h)
            //debug(boat[nh][pl - 1])
        }
        sort(s.begin(), s.end(), customsort);
        //print2(s);
        for (auto &[val, h] : s) {
            int nh = mx - h + 1;
            if (v[p].S == 0) break;
            boat[nh][pl] = val + 1;
            for (int pll = pl + 1; pll <= n; ++pll) boat[nh][pll] = val + 1;
            v[p].S--;
            tnf += boat[nh][pl];
        }
        //print(boat);
    }
    cout<<tnf<<'\n';
}
#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...
#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...