oj.uz

Submission #544669

# Submission time Handle Problem Language Result Execution time Memory
544669 2022-04-02T14:19:32 Z pokmui9909 탐사 (KOI13_probe) C++17
19 / 19
 1 ms 340 KB 
#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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 308 KB Output is correct

Subtask #2
2.09 / 2.09

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

Subtask #3
1.33 / 1.33

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 0 ms 212 KB Output is correct

Subtask #4
5.13 / 5.13

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct

Subtask #5
3.61 / 3.61

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct

Subtask #6
4.37 / 4.37

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct