oj.uz

Submission #173482

# Submission time Handle Problem Language Result Execution time Memory
173482 2020-01-04T09:00:14 Z jhwest2 별자리 2 (JOI14_constellation2) C++14
55 / 100
 9000 ms 504 KB 
#include <bits/stdc++.h>
#define va first
#define vb second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

int N;
ll X[3030], Y[3030], C[3030];
int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);

	cin >> N;
	for (int i=0; i<N; i++) {
		cin >> X[i] >> Y[i] >> C[i];
	}

	ll ans = 0;
	for (int i=0; i<N; i++) {
		for (int j=i+1; j<N; j++) {
			int cnt[3][2]; memset(cnt, 0, sizeof cnt);
			for (int k=0; k<N; k++) {
				ll t = (X[k]-X[i])*(Y[j]-Y[i]) - (X[j]-X[i])*(Y[k]-Y[i]);

				if (t == 0) continue;
				t = t>0 ? 0 : 1;
				cnt[C[k]][t]++;
			}

			ll li=1, lj=1, ri=1, rj=1;
			for (int k=0; k<3; k++) {
				if (C[i] != k) li *= cnt[k][0], ri *= cnt[k][1];
				if (C[j] != k) lj *= cnt[k][0], rj *= cnt[k][1];
			}
			ans += li*rj + lj*ri;
		}
	}

	cout << ans/2;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 7 ms 376 KB Output is correct
4 Correct 14 ms 376 KB Output is correct
5 Correct 32 ms 376 KB Output is correct
6 Correct 101 ms 376 KB Output is correct
7 Correct 101 ms 376 KB Output is correct
8 Correct 100 ms 376 KB Output is correct
9 Correct 101 ms 376 KB Output is correct
10 Correct 59 ms 376 KB Output is correct
11 Correct 102 ms 408 KB Output is correct
12 Correct 105 ms 376 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1863 ms 428 KB Output is correct
2 Correct 2658 ms 476 KB Output is correct
3 Correct 3791 ms 432 KB Output is correct
4 Correct 3636 ms 504 KB Output is correct
5 Execution timed out 9039 ms 376 KB Time limit exceeded
6 Halted 0 ms 0 KB -