제출 #1370132

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1370132		coin_	Uiro (JOI25_uiro)	C++20	0 / 100	5093 ms	3900 KiB

Main

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int inf = 1e9 + 7;

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    int n, q;
    cin >> n;
    vector<int> a(n+1, 0);
    for (int i = 1; i <= n; i++){
        cin >> a[i];
    }
    cin >> q;
    // if (q <= 20){
        // do regretful greedy
        for (int j = 0; j < q; j++){
            int l, r;
            cin >> l >> r;
            priority_queue<int> pq;
            pq.push(-inf);
            int cur = 0, ans = 0;
            for (int i = l; i <= r; i++){
                if (cur - a[i] >= 0){
                    cur -= a[i];
                    pq.push(a[i]);
                    ans++;
                }
                else{
                    // check if can untake largest one
                    int tp = pq.top();
                    if (a[i] < tp){
                        // then take;
                        cur += tp - a[i];
                        pq.pop();
                        pq.push(a[i]);
                    }
                    else{
                        cur += a[i];
                    }
                }
            }
            cout << ans << "\n";
        }
    // }

}

• 서브태스크 1: 0 / 0
• 서브태스크 2: 0 / 3
• 서브태스크 3: 0 / 5
• 서브태스크 4: 0 / 7
• 서브태스크 5: 0 / 15
• 서브태스크 6: 0 / 21
• 서브태스크 7: 0 / 29
• 서브태스크 8: 0 / 20