답안 #116125

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
116125	2019-06-10T16:38:55 Z	shayan_p	Arranging Tickets (JOI17_arranging_tickets)	C++14	10 / 100	1761 ms	512 KB

arranging_tickets

// High above the clouds there is a rainbow...

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int maxn=30,mod=1e9+7;
const ll inf=1e18;

int a[maxn],b[maxn];
ll c[maxn],val[maxn];

int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    
    int n,m; cin>>n>>m;

    for(int i=0;i<m;i++){
	cin>>a[i]>>b[i]>>c[i]; --a[i],--b[i];
    }
    ll ans=inf;
    for(int msk=0;msk<(1<<m);msk++){
	memset(val,0,sizeof val);
	for(int i=0;i<m;i++){
	    if(bit(msk,i)){
		for(int j=a[i];j!=b[i];j=(j+1)%n){
		    val[j]+=c[i];
		}
	    }
	    else{
		for(int j=b[i];j!=a[i];j=(j+1)%n){
		    val[j]+=c[i];
		}
	    }	 
	}
	ll mx=0;
	for(int i=0;i<n;i++){
	    mx=max(mx,val[i]);
	}
	ans=min(ans,mx);
    }
    return cout<<ans<<endl,0;
}
// Deathly mistakes:
//  * Read the problem curfully.
//  * Check maxn.
//  * Overflows.

Subtask #1

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1653 ms	408 KB	Output is correct
2	Correct	1648 ms	376 KB	Output is correct
3	Correct	1587 ms	504 KB	Output is correct
4	Correct	1596 ms	384 KB	Output is correct
5	Correct	1640 ms	384 KB	Output is correct
6	Correct	1761 ms	476 KB	Output is correct
7	Correct	1633 ms	504 KB	Output is correct
8	Correct	1584 ms	376 KB	Output is correct
9	Correct	1668 ms	508 KB	Output is correct
10	Correct	1667 ms	384 KB	Output is correct
11	Correct	1633 ms	384 KB	Output is correct
12	Correct	1695 ms	412 KB	Output is correct
13	Correct	1674 ms	384 KB	Output is correct
14	Correct	1583 ms	504 KB	Output is correct
15	Correct	1718 ms	376 KB	Output is correct

Subtask #2

0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1653 ms	408 KB	Output is correct
2	Correct	1648 ms	376 KB	Output is correct
3	Correct	1587 ms	504 KB	Output is correct
4	Correct	1596 ms	384 KB	Output is correct
5	Correct	1640 ms	384 KB	Output is correct
6	Correct	1761 ms	476 KB	Output is correct
7	Correct	1633 ms	504 KB	Output is correct
8	Correct	1584 ms	376 KB	Output is correct
9	Correct	1668 ms	508 KB	Output is correct
10	Correct	1667 ms	384 KB	Output is correct
11	Correct	1633 ms	384 KB	Output is correct
12	Correct	1695 ms	412 KB	Output is correct
13	Correct	1674 ms	384 KB	Output is correct
14	Correct	1583 ms	504 KB	Output is correct
15	Correct	1718 ms	376 KB	Output is correct
16	Runtime error	2 ms	512 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
17	Halted	0 ms	0 KB	-

Subtask #3

0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1653 ms	408 KB	Output is correct
2	Correct	1648 ms	376 KB	Output is correct
3	Correct	1587 ms	504 KB	Output is correct
4	Correct	1596 ms	384 KB	Output is correct
5	Correct	1640 ms	384 KB	Output is correct
6	Correct	1761 ms	476 KB	Output is correct
7	Correct	1633 ms	504 KB	Output is correct
8	Correct	1584 ms	376 KB	Output is correct
9	Correct	1668 ms	508 KB	Output is correct
10	Correct	1667 ms	384 KB	Output is correct
11	Correct	1633 ms	384 KB	Output is correct
12	Correct	1695 ms	412 KB	Output is correct
13	Correct	1674 ms	384 KB	Output is correct
14	Correct	1583 ms	504 KB	Output is correct
15	Correct	1718 ms	376 KB	Output is correct
16	Runtime error	2 ms	512 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
17	Halted	0 ms	0 KB	-

Subtask #4

0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1653 ms	408 KB	Output is correct
2	Correct	1648 ms	376 KB	Output is correct
3	Correct	1587 ms	504 KB	Output is correct
4	Correct	1596 ms	384 KB	Output is correct
5	Correct	1640 ms	384 KB	Output is correct
6	Correct	1761 ms	476 KB	Output is correct
7	Correct	1633 ms	504 KB	Output is correct
8	Correct	1584 ms	376 KB	Output is correct
9	Correct	1668 ms	508 KB	Output is correct
10	Correct	1667 ms	384 KB	Output is correct
11	Correct	1633 ms	384 KB	Output is correct
12	Correct	1695 ms	412 KB	Output is correct
13	Correct	1674 ms	384 KB	Output is correct
14	Correct	1583 ms	504 KB	Output is correct
15	Correct	1718 ms	376 KB	Output is correct
16	Runtime error	2 ms	512 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
17	Halted	0 ms	0 KB	-

Subtask #5

0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1653 ms	408 KB	Output is correct
2	Correct	1648 ms	376 KB	Output is correct
3	Correct	1587 ms	504 KB	Output is correct
4	Correct	1596 ms	384 KB	Output is correct
5	Correct	1640 ms	384 KB	Output is correct
6	Correct	1761 ms	476 KB	Output is correct
7	Correct	1633 ms	504 KB	Output is correct
8	Correct	1584 ms	376 KB	Output is correct
9	Correct	1668 ms	508 KB	Output is correct
10	Correct	1667 ms	384 KB	Output is correct
11	Correct	1633 ms	384 KB	Output is correct
12	Correct	1695 ms	412 KB	Output is correct
13	Correct	1674 ms	384 KB	Output is correct
14	Correct	1583 ms	504 KB	Output is correct
15	Correct	1718 ms	376 KB	Output is correct
16	Runtime error	2 ms	512 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
17	Halted	0 ms	0 KB	-