Submission #126544

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
126544	2019-07-08T04:05:34 Z	baluteshih	Arranging Tickets (JOI17_arranging_tickets)	C++14	10 / 100	178 ms	508 KB

arranging_tickets

#include <bits/stdc++.h>
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pb push_back
#define MP make_pair
#define F first
#define S second
#define MEM(i,j) memset(i,j,sizeof i)
#define ALL(v) v.begin(),v.end()
#define ET cout << "\n"
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

struct mode
{
	int a,b,w;
}arr[100005];

int sum[200005];
const int INF=1e9;

int main()
{jizz
	int n,m,ans=INF;
	cin >> n >> m;
	for(int i=0;i<m;++i)
	{
		cin >> arr[i].a >> arr[i].b >> arr[i].w;
		if(arr[i].a>arr[i].b)
			swap(arr[i].a,arr[i].b);
	}
	for(int i=(1<<m)-1;i>=0;--i)
	{
		for(int j=1;j<=n;++j)
			sum[j]=0;
		for(int j=0;j<m;++j)
			if(i>>j&1)
				sum[arr[j].a]+=arr[j].w,sum[arr[j].b]-=arr[j].w;
			else
				sum[1]+=arr[j].w,sum[arr[j].a]-=arr[j].w,sum[arr[j].b]+=arr[j].w;
		for(int j=1;j<=n;++j)
			sum[j]+=sum[j-1];
		ans=min(ans,*max_element(sum+1,sum+n+1));
	}
	cout << ans << "\n";
}

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	175 ms	504 KB	Output is correct
2	Correct	175 ms	508 KB	Output is correct
3	Correct	175 ms	376 KB	Output is correct
4	Correct	174 ms	424 KB	Output is correct
5	Correct	175 ms	420 KB	Output is correct
6	Correct	175 ms	504 KB	Output is correct
7	Correct	175 ms	376 KB	Output is correct
8	Correct	176 ms	504 KB	Output is correct
9	Correct	174 ms	504 KB	Output is correct
10	Correct	175 ms	400 KB	Output is correct
11	Correct	175 ms	404 KB	Output is correct
12	Correct	174 ms	376 KB	Output is correct
13	Correct	175 ms	380 KB	Output is correct
14	Correct	175 ms	424 KB	Output is correct
15	Correct	178 ms	424 KB	Output is correct

Subtask #2

0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	175 ms	504 KB	Output is correct
2	Correct	175 ms	508 KB	Output is correct
3	Correct	175 ms	376 KB	Output is correct
4	Correct	174 ms	424 KB	Output is correct
5	Correct	175 ms	420 KB	Output is correct
6	Correct	175 ms	504 KB	Output is correct
7	Correct	175 ms	376 KB	Output is correct
8	Correct	176 ms	504 KB	Output is correct
9	Correct	174 ms	504 KB	Output is correct
10	Correct	175 ms	400 KB	Output is correct
11	Correct	175 ms	404 KB	Output is correct
12	Correct	174 ms	376 KB	Output is correct
13	Correct	175 ms	380 KB	Output is correct
14	Correct	175 ms	424 KB	Output is correct
15	Correct	178 ms	424 KB	Output is correct
16	Incorrect	11 ms	376 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #3

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	175 ms	504 KB	Output is correct
2	Correct	175 ms	508 KB	Output is correct
3	Correct	175 ms	376 KB	Output is correct
4	Correct	174 ms	424 KB	Output is correct
5	Correct	175 ms	420 KB	Output is correct
6	Correct	175 ms	504 KB	Output is correct
7	Correct	175 ms	376 KB	Output is correct
8	Correct	176 ms	504 KB	Output is correct
9	Correct	174 ms	504 KB	Output is correct
10	Correct	175 ms	400 KB	Output is correct
11	Correct	175 ms	404 KB	Output is correct
12	Correct	174 ms	376 KB	Output is correct
13	Correct	175 ms	380 KB	Output is correct
14	Correct	175 ms	424 KB	Output is correct
15	Correct	178 ms	424 KB	Output is correct
16	Incorrect	11 ms	376 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #4

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	175 ms	504 KB	Output is correct
2	Correct	175 ms	508 KB	Output is correct
3	Correct	175 ms	376 KB	Output is correct
4	Correct	174 ms	424 KB	Output is correct
5	Correct	175 ms	420 KB	Output is correct
6	Correct	175 ms	504 KB	Output is correct
7	Correct	175 ms	376 KB	Output is correct
8	Correct	176 ms	504 KB	Output is correct
9	Correct	174 ms	504 KB	Output is correct
10	Correct	175 ms	400 KB	Output is correct
11	Correct	175 ms	404 KB	Output is correct
12	Correct	174 ms	376 KB	Output is correct
13	Correct	175 ms	380 KB	Output is correct
14	Correct	175 ms	424 KB	Output is correct
15	Correct	178 ms	424 KB	Output is correct
16	Incorrect	11 ms	376 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #5

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	175 ms	504 KB	Output is correct
2	Correct	175 ms	508 KB	Output is correct
3	Correct	175 ms	376 KB	Output is correct
4	Correct	174 ms	424 KB	Output is correct
5	Correct	175 ms	420 KB	Output is correct
6	Correct	175 ms	504 KB	Output is correct
7	Correct	175 ms	376 KB	Output is correct
8	Correct	176 ms	504 KB	Output is correct
9	Correct	174 ms	504 KB	Output is correct
10	Correct	175 ms	400 KB	Output is correct
11	Correct	175 ms	404 KB	Output is correct
12	Correct	174 ms	376 KB	Output is correct
13	Correct	175 ms	380 KB	Output is correct
14	Correct	175 ms	424 KB	Output is correct
15	Correct	178 ms	424 KB	Output is correct
16	Incorrect	11 ms	376 KB	Output isn't correct
17	Halted	0 ms	0 KB	-