Submission #56350

ソースコード

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
//sub-BOF
//#define _AOJ_
/*vvv>
zzzzzI
.---. zzuzuI .vgggg&,.
+++++= dAC:|I .WbbWo JMM9^```?TMB` ..&gNNg,. gggggggJ, qgggggggg] (&&&&&&&&[ c+OA&J, (&&&&&&+J, .cJeAA&-. (&&&&&&&&x .&AA&=-.
+++++= dTqk|I Xpbpbp JM#` (M#^ ?MMp MM| +TMN. JMF ' |yk ` dVY 7Vk, Vy XV cVf ?Y! JM V$ `
+++++= dcf:|I Xppppp dMN .MM+ .MM MM| MM] JMMMMMM+ |@tqkoh) ,y0 (V$ yyyyyyyV7 VV JMWyZWr TWVVVVW&,
++++++ d7qk|0 Xppppp ^HMN, _.db WMm, .MMF MM| ..MM` JMF . |yk .WV&. .XW' yy 4yn. jyn +. JM #S
`++++` ?ZZZX= ?WWWW= -THMMMMH9^ (TMMMMM9! MMMMMMM"" JMMMMMMMME |UU. ?TUUUUY= UU. (UU- ^7TUUUV7! JUUUUUUUU 7TUNKO*/
//basic
#include "bits/stdc++.h"
using namespace std;
typedef long long lint;
typedef long double ld;
typedef string cs;
#define all(v) v.begin(),v.end()
#define pb push_back
//rep
#define _vcppunko4(tuple) _getname4 tuple
#define _getname4(_1,_2,_3,_4,name,...) name
#define _getname3(_1,_2,_3,name,...) name
#define _trep2(tuple) _rep2 tuple
#define _trep3(tuple) _rep3 tuple
#define _trep4(tuple) _rep4 tuple
#define _rep1(n) for(lint i=0;i<n;++i)
#define _rep2(i,n) for(lint i=0;i<n;++i)
#define _rep3(i,a,b) for(lint i=a;i<b;++i)
#define _rep4(i,a,b,c) for(lint i=a;i<b;i+=c)
#define _trrep2(tuple) _rrep2 tuple
#define _trrep3(tuple) _rrep3 tuple
#define _trrep4(tuple) _rrep4 tuple
#define _rrep1(n) for(lint i=n-1;i>=0;--i)
#define _rrep2(i,n) for(lint i=n-1;i>=0;--i)
#define _rrep3(i,a,b) for(lint i=b-1;i>=a;--i)
#define _rrep4(i,a,b,c) for(lint i=a+(b-a-1)/c*c;i>=a;i-=c)
#define rep(...) _vcppunko4((__VA_ARGS__,_trep4,_trep3,_trep2,_rep1))((__VA_ARGS__))
#define per(...) _vcppunko4((__VA_ARGS__,_trrep4,_trrep3,_trrep2,_rrep1))((__VA_ARGS__))
#define each(c) for(auto e:c)
//io
template<class T>
istream& operator>>(istream& is,vector<T>& vec);
template<class T,size_t size>
istream& operator>>(istream& is,array<T,size>& vec);
template<class T,class L>
istream& operator>>(istream& is,pair<T,L>& p);
template<class T>
ostream& operator<<(ostream& os,vector<T>& vec);
template<class T,class L>
ostream& operator<<(ostream& os,pair<T,L>& p);
template<class T>
istream& operator>>(istream& is,vector<T>& vec){ for(T& x: vec) is>>x;return is; }
template<class T,class L>
istream& operator>>(istream& is,pair<T,L>& p){ is>>p.first;is>>p.second;return is; }
template<class T,class L>
ostream& operator<<(ostream& os,pair<T,L>& p){ os<<p.first<<" "<<p.second;return os; }
template<class T>
ostream& operator<<(ostream& os,vector<T>& vec){ os<<vec[0];rep(i,1,vec.size())os<<' '<<vec[i];return os; }
template<class T>
ostream& operator<<(ostream& os,deque<T>& deq){ os<<deq[0];rep(i,1,deq.size())os<<' '<<deq[i];return os; }
inline void in(){}
template <class Head,class... Tail>
inline void in(Head&& head,Tail&&... tail){ cin>>head;in(move(tail)...); }
inline bool out(){ return(cout<<'\n',0); }
template <class T>
inline bool out(T t){ return(cout<<t<<'\n',0); }
template <class Head,class... Tail>
inline bool out(Head head,Tail... tail){ cout<<head<<' ';out(move(tail)...);return 0; }
template <class T>
inline void alloc(T &c,lint s){ rep(c.size())c[i].resize(s); }
#define alc alloc
//TA
#define each(c) for(auto &e:c)
#define lin(...) lint __VA_ARGS__;in(__VA_ARGS__)
#define stin(...) string __VA_ARGS__;in(__VA_ARGS__)
#define vin(type,name,size) vector<type> name(size);in(name)
#define fi e.first
#define se e.second
#define YES(c) cout<<((c)?"YES\n":"NO\n"),0
#define Yes(c) cout<<((c)?"Yes\n":"No\n"),0
#define POSSIBLE(c) cout<<((c)?"POSSIBLE\n":"IMPOSSIBLE\n"),0
#define Possible(c) cout<<((c)?"Possible\n":"Impossible\n"),0
#define o(p) cout<<p<<endl,0
#define sp(p) cout<<p<<" "
#define no(p) cout<<p
#define chmin(l,r) l=min(l,r)
#define chmax(l,r) l=max(l,r)
#define ve(type) vector<type>
//other
#ifdef __ENV_TQK__
#define deb(p) cout<<p<<endl,0
#else
#define deb(p) 0
#endif
struct Fastio{
Fastio(){
cin.tie(0),cout.tie(0);
ios::sync_with_stdio(0);
cout<<fixed<<setprecision(10);
}
} __fastio;
//mint
#define md_tmp template<uint_fast64_t md=1000000007>
md_tmp class mint{
using u64=uint_fast64_t;
public:
u64 a;
constexpr mint(const u64 x=0) noexcept: a(x%md){}
constexpr u64 &value() noexcept{ return a; }
constexpr const u64 &value() const noexcept{ return a; }
constexpr mint operator+(const mint rhs) const noexcept{
return mint(*this)+=rhs;
}
constexpr mint operator-(const mint rhs) const noexcept{
return mint(*this)-=rhs;
}
constexpr mint operator*(const mint rhs) const noexcept{
return mint(*this)*=rhs;
}
constexpr mint operator^(const lint rhs) const noexcept{
return mint(*this)^=rhs;
}
constexpr mint operator/(const mint rhs) const noexcept{
return mint(*this)/=rhs;
}
constexpr mint &operator+=(const mint rhs) noexcept{
a+=rhs.a;
if(a>=md)a-=md;
return *this;
}
constexpr mint &operator-=(const mint rhs) noexcept{
if(a<rhs.a)a+=md;
a-=rhs.a;
return *this;
}
constexpr mint &operator*=(const mint rhs) noexcept{
a=a*rhs.a%md;
return *this;
}
constexpr mint &operator^=(const lint rhs) noexcept{
if(!rhs)return *this=1;
u64 exp=rhs-1;
mint base=this->a;
while(exp){
if(exp&1)*this*=base;
base*=base;
exp>>=1;
}
return *this;
}
constexpr mint &operator/=(const mint rhs) noexcept{
a=(*this*(rhs^(md-2))).a;
return *this;
}
};
md_tmp istream& operator>>(istream& os,mint<md>& m){
os>>m.a,m.a%=md;
return os;
}
md_tmp ostream& operator<<(ostream& os,const mint<md>& m){
return os<<m.a;
}
md_tmp mint<md> ncr(lint n,lint r){
if(n<r||n<0||r<0)return mint<md>(0);
mint<md>ncr_res=1,ncr_div=1;
rep(r)ncr_res*=(n-i),ncr_div*=(r-i);
return ncr_res/ncr_div;
}
#ifndef _AOJ_
mint<> operator""m(unsigned long long n){ return mint<>(n); }
mint<998244353> operator""m9(unsigned long long n){ return mint<998244353>(n); }
mint<1000003> operator""m3(unsigned long long n){ return mint<1000003>(n); }
#endif
//const
#define linf 1152921504606846976
#define inf linf
#define MAXN 330
#define md_1e9_7 1000000007
#define md_998244353 998244353
#define pi 3.14159265358979323846
//#define mod md_1e9_7
const int d4[5]={0,1,0,-1,0};
class P{ public:lint f,s; P(lint a,lint b):f(a),s(b){}; P():f(0),s(0){}; };
istream& operator>>(istream& os,P& p){ os>>p.f>>p.s;return os; }
bool operator<(const P& l,const P& r){ return(l.f-r.f?l.f<r.f:l.s<r.s); }
bool operator>(const P& l,const P& r){ return(l.f-r.f?l.f>r.f:l.s>r.s); }
P dp[1l<<20];
int main(){
lint n;in(n);
vector<vector<lint>> a(n);alloc(a,n),in(a);
rep(S,1l<<20)dp[S]=P(inf,0);
dp[0]=P(0,0);
rep(S,1l<<n){
rep(b,n)if(!(S&(1l<<b))){
rep(c,n)if(!(dp[S].s&(1l<<c))){
chmin(dp[S+(1l<<b)],P(dp[S].f+a[b][c],dp[S].s+(1l<<c)));
}
}
}
out(dp[(1l<<n)-1].f);
}
//sub-EOF

ステータス

項目 データ
問題 1108 - 発表会
ユーザー名 Tqk
投稿日時 2019-11-13 00:44:47
言語 C++14
状態 Accepted
得点 1
ソースコード長 7130 Byte
最大実行時間 673 ms
最大メモリ使用量 17132 KB

セット

セット 得点 Cases
1 ALL 1 / 1 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
case01.in AC 612 ms 16856 KB
1
case02.in AC 608 ms 16928 KB
1
case03.in AC 598 ms 17000 KB
1
case04.in AC 598 ms 17072 KB
1
case05.in AC 673 ms 16884 KB
1
case06.in AC 605 ms 16956 KB
1
case07.in AC 612 ms 16908 KB
1
case08.in AC 585 ms 16980 KB
1
case09.in AC 621 ms 17048 KB
1
case10.in AC 603 ms 16988 KB
1
case11.in AC 645 ms 16940 KB
1
case12.in AC 655 ms 17016 KB
1
case13.in AC 584 ms 16964 KB
1
case14.in AC 620 ms 17044 KB
1
case15.in AC 629 ms 17120 KB
1
case16.in AC 627 ms 17060 KB
1
case17.in AC 580 ms 17132 KB
1
case18.in AC 622 ms 17076 KB
1
case19.in AC 601 ms 17024 KB
1
case20.in AC 610 ms 16976 KB
1
sample01.in AC 44 ms 17052 KB
1
sample02.in AC 27 ms 17008 KB
1