Submission #21338

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
21338	2017-04-13T10:31:47 Z	Ushio	Arranging Tickets (JOI17_arranging_tickets)	C++14	10 / 100	206 ms	2180 KB

arranging_tickets

#include <bits/stdc++.h>
#define SZ(x) ((int) (x).size())
using namespace std;

typedef long long i64;

const int INF = 0x3f3f3f3f;
const int NMAX = 6007;

int main() {
    #ifdef LOCAL_RUN
    freopen("task.in", "r", stdin);
    freopen("task.out", "w", stdout);
    //freopen("task.err", "w", stderr);
    #endif // ONLINE_JUDGE
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;

    vector<int> left(m), right(m);
    for (int i = 0; i < m; ++i) {
        int x;
        cin >> left[i] >> right[i] >> x;
        if (left[i] > right[i]) {
            swap(left[i], right[i]);
        }
        left[i]--; right[i]--;
    }

    int ans = INF;
    for (int conf = 0; conf < (1 << m); ++conf) {
        vector<int> cnt(n, 0);
        for (int i = 0; i < m; ++i) {
            if (conf & (1 << i)) {
                cnt[0]++;
                cnt[left[i]]--;
                cnt[right[i]]++;
            } else {
                cnt[left[i]]++;
                cnt[right[i]]--;
            }
        }
        for (int i = 1; i < n; ++i) {
            cnt[i] += cnt[i - 1];
        }
        ans = min(ans, *max_element(cnt.begin(), cnt.end()));
    }
    cout << ans << '\n';
}

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	199 ms	2180 KB	Output is correct
2	Correct	199 ms	2180 KB	Output is correct
3	Correct	206 ms	2180 KB	Output is correct
4	Correct	203 ms	2180 KB	Output is correct
5	Correct	196 ms	2180 KB	Output is correct
6	Correct	199 ms	2180 KB	Output is correct
7	Correct	199 ms	2180 KB	Output is correct
8	Correct	203 ms	2180 KB	Output is correct
9	Correct	203 ms	2180 KB	Output is correct
10	Correct	203 ms	2180 KB	Output is correct
11	Correct	199 ms	2180 KB	Output is correct
12	Correct	203 ms	2180 KB	Output is correct
13	Correct	203 ms	2180 KB	Output is correct
14	Correct	199 ms	2180 KB	Output is correct
15	Correct	203 ms	2180 KB	Output is correct

Subtask #2

0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	199 ms	2180 KB	Output is correct
2	Correct	199 ms	2180 KB	Output is correct
3	Correct	206 ms	2180 KB	Output is correct
4	Correct	203 ms	2180 KB	Output is correct
5	Correct	196 ms	2180 KB	Output is correct
6	Correct	199 ms	2180 KB	Output is correct
7	Correct	199 ms	2180 KB	Output is correct
8	Correct	203 ms	2180 KB	Output is correct
9	Correct	203 ms	2180 KB	Output is correct
10	Correct	203 ms	2180 KB	Output is correct
11	Correct	199 ms	2180 KB	Output is correct
12	Correct	203 ms	2180 KB	Output is correct
13	Correct	203 ms	2180 KB	Output is correct
14	Correct	199 ms	2180 KB	Output is correct
15	Correct	203 ms	2180 KB	Output is correct
16	Incorrect	6 ms	2180 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #3

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	199 ms	2180 KB	Output is correct
2	Correct	199 ms	2180 KB	Output is correct
3	Correct	206 ms	2180 KB	Output is correct
4	Correct	203 ms	2180 KB	Output is correct
5	Correct	196 ms	2180 KB	Output is correct
6	Correct	199 ms	2180 KB	Output is correct
7	Correct	199 ms	2180 KB	Output is correct
8	Correct	203 ms	2180 KB	Output is correct
9	Correct	203 ms	2180 KB	Output is correct
10	Correct	203 ms	2180 KB	Output is correct
11	Correct	199 ms	2180 KB	Output is correct
12	Correct	203 ms	2180 KB	Output is correct
13	Correct	203 ms	2180 KB	Output is correct
14	Correct	199 ms	2180 KB	Output is correct
15	Correct	203 ms	2180 KB	Output is correct
16	Incorrect	6 ms	2180 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #4

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	199 ms	2180 KB	Output is correct
2	Correct	199 ms	2180 KB	Output is correct
3	Correct	206 ms	2180 KB	Output is correct
4	Correct	203 ms	2180 KB	Output is correct
5	Correct	196 ms	2180 KB	Output is correct
6	Correct	199 ms	2180 KB	Output is correct
7	Correct	199 ms	2180 KB	Output is correct
8	Correct	203 ms	2180 KB	Output is correct
9	Correct	203 ms	2180 KB	Output is correct
10	Correct	203 ms	2180 KB	Output is correct
11	Correct	199 ms	2180 KB	Output is correct
12	Correct	203 ms	2180 KB	Output is correct
13	Correct	203 ms	2180 KB	Output is correct
14	Correct	199 ms	2180 KB	Output is correct
15	Correct	203 ms	2180 KB	Output is correct
16	Incorrect	6 ms	2180 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #5

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	199 ms	2180 KB	Output is correct
2	Correct	199 ms	2180 KB	Output is correct
3	Correct	206 ms	2180 KB	Output is correct
4	Correct	203 ms	2180 KB	Output is correct
5	Correct	196 ms	2180 KB	Output is correct
6	Correct	199 ms	2180 KB	Output is correct
7	Correct	199 ms	2180 KB	Output is correct
8	Correct	203 ms	2180 KB	Output is correct
9	Correct	203 ms	2180 KB	Output is correct
10	Correct	203 ms	2180 KB	Output is correct
11	Correct	199 ms	2180 KB	Output is correct
12	Correct	203 ms	2180 KB	Output is correct
13	Correct	203 ms	2180 KB	Output is correct
14	Correct	199 ms	2180 KB	Output is correct
15	Correct	203 ms	2180 KB	Output is correct
16	Incorrect	6 ms	2180 KB	Output isn't correct
17	Halted	0 ms	0 KB	-