Submission #544669

#	Time	Username	Problem	Language	Result	Execution time	Memory
544669		pokmui9909	탐사 (KOI13_probe)	C++17	19 / 19	1 ms	340 KiB

probe

#include <string>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <deque>
#include <functional>
#include <climits>
#include <set>
#include <map>
#include <cassert>
#include <cmath>
using namespace std;

struct info
{
    int s, e, c;
};
vector<info> V;
int dist[1005];
const int INF = 1e9;

int main()
{
    cin.tie(0); cout.tie(0);
    //ios_base::sync_with_stdio(false);

    int n, k; cin >> n >> k;
    for (int i = 0; i < k; i++)
    {
        int s, e, c; cin >> s >> e >> c;
        V.push_back({ s - 1, e, c });
    }
    for(int i = 0; i <= n; i++)
        dist[i] = i;
    for(int i = 1; i <= n; i++)
    {
        for(auto j : V)
        {
            int s = j.s, e = j.e, c = j.c;
            if(dist[e] - dist[s] == c) continue;
            if(i == n)
            {
                cout << "NONE";
                return 0;
            }
            int p = dist[s] + c;
            if(dist[e] > p)
            {
                for(int x = 0; x < e; x++) dist[x] = min(dist[x], p);
                for(int x = e; x <= n; x++) dist[x] = min(dist[x], x - e + p);
            }
            else
            {
                p = dist[e] - c;
                for(int x = 0; x < s; x++) dist[x] = min(dist[x], p);
                for(int x = s; x <= n; x++) dist[x] = min(dist[x], x - s + p);
            }

            //for(int x = 0; x <= n; x++) cout << dist[x] << ' '; cout << '\n';
        }
    }
    for(int i = 1; i <= n; i++)
        cout << (dist[i - 1] != dist[i] ? '#' : '-');
}

• Subtask 1: 2.47 / 2.47
• Subtask 2: 2.09 / 2.09
• Subtask 3: 1.33 / 1.33
• Subtask 4: 5.13 / 5.13
• Subtask 5: 3.61 / 3.61
• Subtask 6: 4.37 / 4.37