제출 #1083609

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1083609		adrilen	Trains (BOI24_trains)	C++17	0 / 100	49 ms	36180 KiB

Main

//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using arr = array<int, 2>;
using arrr = array<int, 3>;

constexpr ll modn = 1e9 + 7, maxn = 1e5 + 5;

ll value[maxn] = { 0 };
// vector<arr> edges[maxn];
map<int, arr> edges[maxn]; // Kan bruke vector siden de minste vil alltid komme sist til en bestemt node

void fadd(ll &a, ll &b)
{
    a += b;
    if (a >= modn) a -= modn;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n;
    cin >> n;

    value[0] = 1;

    ll output = 0;

    int d, x;
    for (int i = 0; i < n; i++)
    {
        cin >> d >> x;
        if (d == 0) continue;
        edges[i][d] = {-1, x};
    }
    

    for (int i = 0; i < n; i++)
    {
        for (auto p : edges[i])
        {

            if (i + p.first >= n) continue;

            if (p.second[0] < 0) 
            {
                p.second[0]++;
                p.second[0] *= -1;
                p.second[0] += value[i];
            }
            // cout << i << " " << value[i] << " | s: " << p.first << " v: " << p.second[0] << " a: " << p.second[1] << "\n";

            // cout << i + p.first << " " << p.second[0] << "\n";
            // fadd(value[i + p.first], p.second[0]);

            value[i + p.first] += p.second[0];
            // cout << value[i + p.first]<< " \n";


            if (edges[i + p.first].count(p.first)) {
                if (edges[i + p.first][p.first][0] < 0) 
                    edges[i + p.first][p.first][0] -= p.second[0];
                else 
                    edges[i + p.first][p.first][0] += p.second[0];
            } else {
                edges[i + p.first][p.first] = {p.second[0], p.second[1]};
            }
        }

        fadd(output, value[i]);
        // cout << "NNNNNNNNNNN'NNNNNNNNNN\t" << i << " " << output << "\n";
    }

    cout << output << "\n";

    // for (int i = 0; i < n; i++)
    // {
    //     cout << i << " " << value[i] << "\n";
    // }

}

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