제출 #1268923

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1268923		top1svtin	Trains (BOI24_trains)	C++20	100 / 100	180 ms	6216 KiB

Main

#include <bits/stdc++.h>

#define kien long long
#define pii pair<int, int>
#define FOR(i, a, b) for (int i = a; i <= b; i++)
#define FORD(i, a, b) for (int i = a; i >= b; i--)
#define Million 1000000
const int MOD = 1e9 + 7;
const int MXN = 2e5 + 5;
const int BASE = 3137;

using namespace std;

kien dp[500][500], ans[200005];
priority_queue<pair<pair<kien,kien>,pair<kien,kien>>, vector<pair<pair<kien,kien>,pair<kien,kien>>>, greater<pair<pair<kien,kien>,pair<kien,kien>>>> ev;

main() {
    kien n; 
    cin >> n; 
    ans[1] = 1; 
    kien sum = 0;
    FOR (i, 1, n) {
        kien d, x; cin >> d >> x;
        for (kien j = 1; j*j < n; j++) {
            ans[i] += dp[i%j][j];
            ans[i] %= 1000000007;
        }
        if (d*d >= n) {
            for (kien j = 1; j <= x and i+j*d <= n; j++) {
            	ans[i+j*d] += ans[i];
            	ans[i+j*d] %= 1000000007;
            }
        } else if (d > 0) {
            dp[i%d][d] += ans[i];
            dp[i%d][d] %= 1000000007;
            ev.push({{i+x*d,ans[i]},{i%d,d}});
        }
        while (!ev.empty() and ev.top().first.first <= i) {
            auto cur = ev.top(); ev.pop();
            dp[cur.second.first][cur.second.second] -= cur.first.second;
            while (dp[cur.second.first][cur.second.second] < 0) {
                dp[cur.second.first][cur.second.second] += 1000000007;
            }
        }
        sum += ans[i]; sum %= 1000000007;
    }
    cout << sum;
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp:17:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   17 | main() {
      | ^~~~

• Subtask 1: 8 / 8
• Subtask 2: 13 / 13
• Subtask 3: 16 / 16
• Subtask 4: 34 / 34
• Subtask 5: 29 / 29