/*
Editor: Abdelrahman Hossam
Nickname: Blobo2_Blobo2
IOI next year isA :)
*/
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-funroll-all-loops,-fpeel-loops,-funswitch-loops")
#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int16_t
#define endl "\n"
#define all(v) v.begin(),v.end()
#define gen(arr,n,nxt) generate(arr,arr+n,nxt)
#define Blobo2_el_7akim_elly_3ayz_yro7_IOI_w_3ayz_yakol_jilaty ios_base::sync_with_stdio(false);cin.tie(0);
#define EPS 0.00000001
const int mo=1e9+7,INF=1e18;
int nxt(){int x;cin>>x;return x;}
int n,m,k,val[101][1001][2];
vector<pair<int,int> > adj[101];
set<vector<int> >cycle;
int now =-1;
int vis[101];
vector<int> nodes;
void store(int u,int start){
for(auto v:adj[u]){
if(v.first == start){
nodes.push_back(nodes[0]);
cycle.insert(nodes);
return;
}
if(vis[v.first] == vis[u]+1){
nodes.push_back(v.first);
store(v.first,start);
}
}
}
void dfs(int u,int par = -1){
if(par == -1)vis[u]=1;
else vis[u] = vis[par] + 1;
for(auto v:adj[u]){
if(!vis[v.first] && v.first > now)
dfs(v.first,u);
else{
nodes.clear();
nodes.push_back(v.first);
store(v.first,v.first);
}
}
vis[u] = 0;
}
int elmostoptimal(int idx = 0,int product = -1){
//cout<<idx<<' '<<endl;
if(idx == nodes.size())
return 0;
int ret = 0;
if(product != -1)
ret = max(ret,elmostoptimal(idx+1,-1) + val[nodes[idx]][product][1]);
ret=max(ret, elmostoptimal(idx+1,product));
for(int i=0;i<k;i++){
if(val[nodes[idx]][i][0] != -1){
if(product!=-1)
ret= max(ret,elmostoptimal(idx+1,i) + (val[nodes[idx]][product][1]-val[nodes[idx]][i][0] ));
else
ret= max(ret,elmostoptimal(idx+1,i) - val[nodes[idx]][i][0]);
}
}
return ret;
}
signed main(){
Blobo2_el_7akim_elly_3ayz_yro7_IOI_w_3ayz_yakol_jilaty
n=nxt(),m=nxt(),k=nxt();
for(int i=0;i<n;i++){
for(int j=0;j<k;j++){
val[i][j][0] = nxt();
val[i][j][1] = nxt();
}
}
int distance[n][n];
memset(distance,0,sizeof distance);
for(int i=0;i<m;i++){
int x=nxt()-1,y=nxt()-1,c=nxt();
adj[x].push_back({y,c});
distance[x][y] = c;
}
for(int i=0;i<n;i++){
now = i;
dfs(i);
memset(vis,0,sizeof vis);
}
int mx = 0;
int dis[cycle.size()];
memset(dis,0,sizeof dis);
int i=0;
for(auto x:cycle){
for(int j=0;j<n;j++){
int u = x[j], v = x[(j+1)%n];
dis[i] += distance[u][v];
}
i++;
}
i=0;
for(auto x:cycle){
nodes.clear();
nodes = x;
/*for(int j=0;j<nodes.size();j++)cout<<nodes[j]<<' ';
cout<<endl;*/
int ans = elmostoptimal();
mx=max(mx,ans / dis[i]);
//cout<<ans<<endl;
i++;
}
cout<<mx;
return 0;
}
Compilation message
merchant.cpp: In function 'long long int elmostoptimal(long long int, long long int)':
merchant.cpp:60:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | if(idx == nodes.size())
| ~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1084 ms |
183388 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1093 ms |
460 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1089 ms |
1100 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1093 ms |
460 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
