akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define REP(i, a, n) for(ll i = ((ll) a); i < ((ll) n); i++)
using namespace std;
typedef long long ll;

ll dd[5] = { 0, 1, 0, -1, 0 }; // right, bottom, left, top
ll dN = 3, dE = 0, dS = 1, dW = 2;

ll H, W;
char S[50][50];
string C;

bool condition(ll y, ll x, ll d, ll &t) {
  bool neg = false, cond = false;
  if(C[t] == '~') {
    neg = true;
    t++;
  }
  if(C[t] == 'N') cond = (d == dN);
  if(C[t] == 'E') cond = (d == dE);
  if(C[t] == 'S') cond = (d == dS);
  if(C[t] == 'W') cond = (d == dW);
  if(C[t] == 'C') cond = (S[y + dd[d]][x + dd[d + 1]] == '#');
  if(C[t] == 'T') cond = true;
  t++;
  return (!neg && cond) || (neg && !cond);
};

int main(void) {
  cin >> H >> W;
  REP(i, 0, H) REP(j, 0, W) cin >> S[i][j];
  cin >> C;

  ll sy, sx, gy, gx;
  REP(i, 0, H) REP(j, 0, W) {
    if(S[i][j] == 's') { sy = i; sx = j; }
    if(S[i][j] == 'g') { gy = i; gx = j; }
  }

  stack<ll> stk;
  vector<ll> jump(C.length(), -1);
  REP(i, 0, C.length()) {
    if(C[i] == '[' || C[i] == '{') stk.push(i);
    else if(C[i] == ']' || C[i] == '}') {
      ll j = stk.top();
      stk.pop();
      jump[i] = j;
      jump[j] = i + 1;
    }
  }

  bool check[H][W][4][C.length()];
  REP(i, 0, H) REP(j, 0, W) REP(k, 0, 4) REP(l, 0, C.length()) check[i][j][k][l] = false;

  ll y = sy, x = sx, d = 3, t = 0, ans = 0;
  while(1) {
    if(y == gy && x == gx) break;

    if(check[y][x][d][t]) break;
    check[y][x][d][t] = true;

    if(C[t] == '[') {
      ll s = t++;
      if(!condition(y, x, d, t)) t = jump[s];
    } else if(C[t] == ']') {
      t++;
    } else if(C[t] == '{') {
      ll s = t++;
      if(!condition(y, x, d, t)) t = jump[s];
    } else if(C[t] == '}') {
      t = jump[t];
    } else {
      if(C[t] == '^') {
        ll ny = y + dd[d], nx = x + dd[d + 1];
        if(S[ny][nx] != '#') { y = ny; x = nx; }
      }
      if(C[t] == 'v') {
        ll ny = y + dd[(d + 2) % 4], nx = x + dd[(d + 3) % 4];
        if(S[ny][nx] != '#') { y = ny; x = nx; }
      }
      if(C[t] == '>') d = (d + 1) % 4;
      if(C[t] == '<') d = (d + 3) % 4;
      t++;
      ans++;
    }
  }

  if(y == gy && x == gx) cout << ans << endl;
  else cout << -1 << endl;
}



Measured memory_bytes: 13008
#include <bits/stdc++.h>
using namespace std;
int main () {
  long N, K;
  cin >> N >> K;
  vector<pair<long, long>> data(N);
  for(int i = 0; i < N; i++)cin >> data.at(i).first;
  for(int i = 0; i < N; i++)cin >> data.at(i).second;
  vector<long> ex(N), sub;
  long a = 0, ans = -10000000000, ring, baf, size;
  for(int i = 0; i < N; i++){
    if(ex.at(i) == 1)continue;
    a = i;
    while(ex.at(a) == 0){
      ex.at(a) = 1;
      sub.push_back(data.at(a).second);
      a = data.at(a).first - 1;
    }
    ring = 0;
    size = sub.size();
    if(K > size){
      for(int j = 0; j < size; j++)ring += sub.at(j);
    }
    for(int j = 0; j < size; j++){
      baf = 0;
      for(int k = 1; k <= min(K,size); k++){
        baf += sub.at((j + k) % size);
        if(ring <= 0){
          ans = max(ans, baf);
        } else {
          ans = max(ans, ((K - k) / size) * ring + baf);
        }
      }
    }
    sub.clear();
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3856
N,*H=`dd`.split.map &:to_i
B=[0]*N*2
N.times{|i|j=k=r=H[i]
1while(r=[r,B[j]+H[N+i]].max;j&=j-1)>0
(B[k]=r;k+=k&-k)while B[k]&.<r}
p B.max

Measured memory_bytes: 61732
#include <bits/stdc++.h>
using namespace std;

int main() {
  
  int H=0, A=0;
  
  cin >> H >> A;
  
  int count=0;
  int sub=H-A;
  int kai=H/A+1;

  if(H%A==0) {
    
    cout << H/A << endl;
    
  } else {
    
    for(int i=0; i<kai; i++) {
  
      sub = sub-A;

      count++;
    
    }
  
    cout << count << endl;
  
  }
  
  return 0;
  
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <numeric>

using namespace std;
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define reppe(i,a,b) for(int i = (int)(a) ; i <= (int)(b) ; ++i)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; --i)
#define repme(i,a,b) for(int i = (int)(a) ; i >= (int)(b) ; --i)

typedef long long ll;

long long GCD(long long a, long long b){if(b==0)return a;return GCD(b,a%b);}

int main() {
    int N; cin >> N;
    vector<ll> A(N); repp(i,0,N) cin >> A[i]; sort(A.begin(), A.end());
    vector<ll> B(N); repp(i,0,N) cin >> B[i]; sort(B.begin(), B.end());
    vector<ll> C(N); repp(i,0,N) cin >> C[i]; sort(C.begin(), C.end());

    vector<ll> countA(N);
    repp(i,0,N) countA[i] = N - (upper_bound(B.begin(), B.end(), A[i]) - B.begin());

    vector<ll> countB(N);
    countB[N-1] = N - (upper_bound(C.begin(), C.end(), B[N-1]) - C.begin());
    repm(i,N-2,-1) countB[i] = countB[i+1] + N - (upper_bound(C.begin(), C.end(), B[i]) - C.begin());

    ll res = 0;
    repp(i,0,N) res += countB[N - countA[i]];
    cout << res << endl;
}



Measured memory_bytes: 4224
#include<bits/stdc++.h>
using namespace std;

int main() {
    int P,Q,R;
    cin >> P >> Q >> R;
    int A_B_C = P + Q;
    int B_C_A = Q + R;
    int C_A_B = R + P;

    int s = min(min(A_B_C,B_C_A), C_A_B);

    cout << s << endl;

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)

int main(){
  int n;
  cin>>n;
  rep(i,10)rep(j,10){
    if(i*j==n){
      cout<<"Yes"<<endl;
      return 0;
    }
  }
  cout<<"No"<<endl;
  return 0;
}

Measured memory_bytes: 3636
N = int(input())
t = [0 for i in range(N + 1)]
x = [0 for i in range(N + 1)]
y = [0 for i in range(N + 1)]
t[0] = 0
x[0] = 0
y[0] = 0

def valid_move(t1, x1, y1, t2, x2, y2):
    d = abs(x1 - x2) + abs(y1 - y2)
    return (t2 - t1) >= d and (t2 - t1) % 2 == d % 2

for i in range(1, N + 1):
    t[i], x[i], y[i] = map(int, input().split())
    
yes = True
for i in range(N):
    if not valid_move(t[i], x[i], y[i], t[i + 1], x[i + 1], y[i + 1]):
        yes = False
        break
        
if yes:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 11816
#include<stdio.h>
int main(void){
  int c500 ,c100 ,c50 ,a , i ,j ,k, count = 0;
  scanf("%d %d %d %d" ,&c500 ,&c100 ,&c50,&a);

  for(i = 0; i <= c500; i++){

    for(j = 0; j <= c100; j++){

    for(k = 0; k <= c50; k++){
    //  printf("%d‚Å%d‚È%d\n",i,j,k);
      if(a == i*500 + j*100 + k*50){
        count ++;
      }
    }
  }
  }
  printf("%d\n",count);
  return 0;


}


Measured memory_bytes: 128
h,w = map(int, input().split())
d = [list(map(int, input().split())) for i in range(10)]

for k in range(10) :
    for i in range(10) :
        for j in range(10) :
            d[i][j] = min(d[i][k]+d[k][j], d[i][j])

ans = 0
for i in range(h):
    v = map(int, input().split())
    for x in v :
        if x >= 0 : ans += d[x][1]

print(ans)


Measured memory_bytes: 3064
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

int cnt[200005],n,q;
vector<int> rad[200005];

void dfs(int now,int add,int from)
{
    add+=cnt[now];
    cnt[now] = add;
    for(int i=0;i<rad[now].size();++i)
    {
        if(rad[now][i]==from) continue;
        dfs(rad[now][i],add,now);
    }
}

int main()
{
    scanf("%d%d",&n,&q);int a,b;
    for(int i=1;i<n;++i){
        scanf("%d%d",&a,&b);
        rad[a].push_back(b);
        rad[b].push_back(a);
    }
    for(int i=0;i<q;++i){
        scanf("%d%d",&a,&b);
        cnt[a]+=b;
    }
    dfs(1,0,-1);
    for(int i=1;i<=n;++i){
        printf("%d ",cnt[i]);
    }
    printf("\n");
    return 0;
}


Measured memory_bytes: 26624
#include<bits/stdc++.h>
#include<algorithm>
#define ll long long
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;
int main()
{
    fast_io
    ll t,i,j,h,w;
    cin>>h>>w;
    char a[h][w];
    for(i=0; i<h; i++)
        for(j=0; j<w; j++)
            cin>>a[i][j];
    for(i=0; i<h; i++)
    {
        for(t=0; t<w; t++)
            cout<<a[i][t];
        cout<<endl;

        for(j=0; j<w; j++)
            cout<<a[i][j];
        cout<<endl;

    }
    return 0;
}





Measured memory_bytes: 3600
// "header" {{{
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <string>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <list>
#include <tuple>
#include <iomanip>

using namespace std;

#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define all(x) (x).begin(),(x).end()
#define pii pair<int,int> 
#define int int64_t
#define Fixed fixed << setprecision(10)
#define moke_pair make_pair
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const long long mod = 1000000007;

constexpr int dx[] = {1,0,-1,0,1,1,-1,-1};
constexpr int dy[] = {0,-1,0,1,1,-1,-1,1};

template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }

template <class T> using min_heap = priority_queue<T,vector<T>,greater<T> >;
template <class T> using max_heap = priority_queue<T>;
template <class T,class U> using umap = unordered_map<T,U>;

inline int64_t updiv(int64_t n,int64_t d){
    return ((n + d -1) / d);
}
/*
inline double Sqrt( const double &x) 
{
	double         xHalf = 0.5 * x;
	int64_t  tmp   = 0x5FE6EB50C7B537AAl - ( *(int64_t*)&x >> 1);
	double         xRes  = * (double*)&tmp;

	xRes *= ( 1.5 - ( xHalf * xRes * xRes ) );
	xRes *= ( 1.5 - ( xHalf * xRes * xRes ) );
	xRes *= ( 1.5 - ( xHalf * xRes * xRes ) );
	xRes *= ( 1.5 - ( xHalf * xRes * xRes ) );
	return xRes * x;
}
*/
// }}}

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int N,W;
    cin >> N >> W;
    vector<int> w(N+1),v(N+1);
    vector<vector<int> > dp(N+1,vector<int>(1e5+1,LINF));
    dp[0][0] = 0;

    rep(i,N){
        cin >> w[i] >> v[i];
        rep(j,1e5){
            chmin(dp[i+1][j],dp[i][j]);
            if(j + v[i] <= 1e5) chmin(dp[i+1][j+v[i]],dp[i][j] + w[i]);
        }
    }

    for(int i = 1e5;i >= 0;--i){
        if(dp[N][i] <= W) return cout << i << '\n',0;
    }

    return 0;
}


Measured memory_bytes: 80256
#include <bits/stdc++.h>
using namespace std;

int main(){
int i=0;
string S,T; cin >> S >> T;
if(S[0]==T[0]){i++;}
if(S[1]==T[1]){i++;}
if(S[2]==T[2]){i++;}
cout << i << "\n";
}

Measured memory_bytes: 256
#include<iostream>
#include<map>
using namespace std;
int main(){
  int N,M;
  string s;
  map<string,int> baket;
  cin>>N;
  for(int i=0;i<N;i++){
    cin>>s;
    baket[s]++;
  }
  cin>>M;
  for(int i=0;i<M;i++){
    cin>>s;
    baket[s]--;
  }
  int max=0;
  for(auto x:baket){
    if(max<x.second)max=x.second;
  }
  cout<<max<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
//#include<fstream>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
#define endl '\n'
#define pb push_back
#define fi first
#define se second
typedef long long ll;
#define double long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define all(con) con.begin(),con.end()
#define w(x) int x; cin>>x; while(x--)
const ll infl=0x3f3f3f3f3f3f3f3fLL;
const int infi=0x3f3f3f3f;
//const int mod=998244353;
const int mod=1000000007;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

/*ofstream fout("bcount.out");
ifstream fin("bcount.in");*/

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cout<<fixed<<setprecision(8);
    int x;
    cin>>x;
    cout<<(x^1)<<endl;
    return 0;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;
using ll = long long;
using P  = pair<int, int>;

int main() {
    int S, W;
    cin >> S >> W;
    if(S > W) {
        cout << "safe" << endl;
    } else {
        cout << "unsafe" << endl;
    }
    return 0;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;

long long int n,m;
long long int dp[1005][1005];


char a[1000][1000];

long long int mod = 1e9+7;
long long int numberPath(int i,int j)
{

    if(i>=n||j>=m)
        return 0;
    if(a[i][j] == '#') return 0;
    if(i==n-1 && j==m-1)
        return 1;

    if(dp[i][j]!=-1)
        return dp[i][j];
    
    return dp[i][j] = (numberPath(i+1,j)%mod+numberPath(i,j+1)%mod)%mod;

}






int main()
{
    cin>>n>>m;
    memset(dp,-1,sizeof(dp));
    for(int i = 0;i<n;i++)
        for(int j =0;j<m;j++)
            cin>>a[i][j];
    cout<<(long long int)numberPath(0,0)<<"\n";

    return 0;
}


Measured memory_bytes: 9216
#include <stdio.h>
#define INF 999

int main(void)
{
	int N, V, graph[20][20], node[20], node2[20], s, t, x, y,i, j, f, g;
	
	scanf("%d%d", &V, &N);
	for (i = 0; i < V; i++)
	{
		for (j = 0; j < V; j++)
			graph[i][j] = INF;
		node[i] = node2[i] = INF;
	}
	for (i = 0; i <= N; i++)
	{
		scanf("%d,%d,%d,%d", &s, &t, &x, &y);
		s--;
		t--;
		if (i != N)
		{
			graph[s][t] = x;
			graph[t][s] = y;
		}
	}
	node[s] = node2[t] = 0;
	while (1)
	{
		f = g = 0;
		for (i = 0; i < V; i++)
			for (j = 0; j < V; j++)
			{
				if (node[i] != INF && graph[i][j] != INF && node[j] > node[i] + graph[i][j])
				{
					f = 1;
					node[j] = node[i] + graph[i][j];
				}
				if (node2[i] != INF && graph[i][j] != INF && node2[j] > node2[i] + graph[i][j])
				{
					g = 1;
					node2[j] = node2[i] + graph[i][j];
				}
			}
			if (!f && !g)
				break;
	}
	printf("%d\n", x - y - node[t] - node2[s]);
	return 0;
}

Measured memory_bytes: 600
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <string>
#include <string.h>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <map>
#include <set>
#include <iostream>
#include <sstream>
#include <numeric>
#include <cctype>
#include <bitset>
#include <cassert>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define gep(i,g,j) for(int i = g.head[j]; i != -1; i = g.e[i].next)
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcount
#define uni(x) x.erase(unique(rng(x)),x.end())
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define df(x) int x = in()
#define dame { puts("-1"); return 0;}
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,vector<T>,greater<T> >
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}
inline void priv(vi a) { rep(i,sz(a)) printf("%d%c",a[i],i==sz(a)-1?'\n':' ');}
template<typename T>istream& operator>>(istream&i,vector<T>&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T>string join(vector<T>&v)
{stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename T>ostream& operator<<(ostream&o,vector<T>&v)
{if(sz(v))o<<join(v);return o;}
template<typename T1,typename T2>istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<typename T1,typename T2>ostream& operator<<(ostream&o,pair<T1,T2>&v)
{return o<<v.fi<<","<<v.se;}
const int MX = 100005, INF = 1001001001;
const ll LINF = 1e18;
const double eps = 1e-10;
typedef vector<string> vs;



int main() {
  int h, w;
  scanf("%d%d",&h,&w);
  vs s(h);
  rep(i,h) cin >> s[i];
  int cnt = 0;
  rep(i,h)rep(j,w) cnt += s[i][j]=='#';
  puts(cnt==h+w-1?"Possible":"Impossible");
  return 0;
}































Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<vector>
#include<string>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<climits>
#include<fstream>

#define MOD (1000000007)

using namespace std;

typedef long long int Int;

int main(void) {
    Int N,K;

    cin>>N>>K;

    Int sum = 0;
    for(int i = 1;i+K-1 <= N;i++)
        sum++;

    cout<<sum<<endl;


    return 0;
}




Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <cmath> 
using namespace std;

int main(){
    string S;
    cin >> S;
    int count = 0;
    for(int i=0;i<4;i++){
        if(S[i] == '+'){
            count++;
        }else{
            count--;
        }
    }

    cout << count << endl;
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <vector>
using namespace std;

namespace zyt
{
	template<typename T>
	inline bool read(T &x)
	{
		char c;
		bool f = false;
		x = 0;
		do
			c = getchar();
		while (c != EOF && c != '-' && !isdigit(c));
		if (c == EOF)
			return false;
		if (c == '-')
			f = true, c = getchar();
		do
			x = x * 10 + c - '0', c = getchar();
		while (isdigit(c));
		if (f)
			x = -x;
		return true;
	}
	template<typename T>
	inline void write(T x)
	{
		static char buf[20];
		char *pos = buf;
		if (x < 0)
			putchar('-'), x = -x;
		do
			*pos++ = x % 10 + '0';
		while (x /= 10);
		while (pos > buf)
			putchar(*--pos);
	}
	typedef pair<int, int> pii;
	typedef long long ll;
	const int N = 1e3 + 10, M = 2e3 + 10, P = 1e9 + 7;
	struct edge
	{
		int u, v, w;
		ll delta;
		bool flag;
	} e[M];
	int n, m, p[N], dep[N], fa[N], w[N];
	ll X;
	vector<pii> g[N];
	int x[N];
	int find(const int x)
	{
		return p[x] ? p[x] = find(p[x]) : x;
	}
	int power(int a, int b)
	{
		int ans = 1;
		while (b)
		{
			if (b & 1)
				ans = (ll)ans * a % P;
			a = (ll)a * a % P;
			b >>= 1;
		}
		return ans;
	}
	void dfs(const int u, const int f)
	{
		dep[u] = dep[f] + 1;
		fa[u] = f;
		for (auto v : g[u])
			if (v.first != f)
				w[v.first] = v.second, dfs(v.first, u);
	}
	int cal(int u, int v)
	{
		int ans = 0;
		if (dep[u] < dep[v])
			swap(u, v);
		while (dep[u] > dep[v])
			ans = max(ans, w[u]), u = fa[u];
		while (u != v)
			ans = max(ans, max(w[u], w[v])), u = fa[u], v = fa[v];
		return ans;
	}
	int work()
	{
		read(n), read(m), read(X);
		for (int i = 1; i <= m; i++)
			read(e[i].u), read(e[i].v), read(e[i].w);
		sort(e + 1, e + m + 1, [](const edge &a, const edge &b){return a.w < b.w; });
		ll sum = 0;
		for (int i = 1; i <= m; i++)
		{
			int u = e[i].u, v = e[i].v;
			if (find(u) != find(v))
			{
				p[find(u)] = find(v), sum += e[i].w, e[i].flag = true;
				g[u].push_back(pii(v, e[i].w));
				g[v].push_back(pii(u, e[i].w));
			}
		}
		if (sum > X)
		{
			puts("0");
			return 0;
		}
		dfs(1, 0);
		int ans = 0;
		if (sum == X)
			ans = ll(power(2, n - 1) - 2 + P) % P * power(2, m - n + 1) % P;
		for (int i = 1; i <= m; i++)
			if (!e[i].flag)
				e[i].delta = e[i].w - cal(e[i].u, e[i].v);
		sort(e + 1, e + m + 1, 
			[](const edge &a, const edge &b){return a.flag ^ b.flag ? a.flag : a.delta < b.delta; });
		for (int i = n; i <= m; i++)
			if (sum + e[i].delta == X)
				ans = (ans + power(2, m - i + 1)) % P;
		write(ans);
		return 0;
	}
}
int main()
{
	return zyt::work();
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;

int G(int A,int B){
  int a,b,r;
  a=max(A,B);
  b=min(A,B);
  r=a%b;
  while(r!=0){
    a=b;
    b=r;
    r=a%b;
  }
  return b;
}

int main(){
  int A,B,K;
  cin>>A>>B>>K;
  int g;
  g=G(A,B);
  int count=0;
  int L;
  
  for(int i=g;count!=K;i--){
    if(g%i==0){
      count++;
      L=i;
    }
  }
  cout<<L;
}

  
  

Measured memory_bytes: 256
N, x = list(map(int, input().split(' ')))
a = list(map(int, input().split(' ')))

count = 0
for i in range(len(a) - 1):
    if a[i] + a[i + 1] > x:
        eat = a[i] + a[i + 1] - x
        if eat <= a[i + 1]:
            a[i + 1] -= eat
        else:
            a[i] = eat - a[i + 1]
            a[i + 1] = 0
        count += eat
print(count)

Measured memory_bytes: 14548
/*in the name of Allah the most beneficent the most merciful.*/
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define MAX 1e18
#define MIN -1e18
#define MOD 1000000007
//#define mod2 20071027
//#define MOD 998244353
// #define base 100001
//#define mod 1000074259
#define base2 31
#define memz(a) memset(a, 0, sizeof(a))
#define memn(a) memset(a, -1, sizeof(a))
#define in1(a) scanf("%lld", &a)
#define in2(a, b) scanf("%lld%lld", &a, &b)
#define TC(c) printf("Case %lld:\n", ++c)
#define out(x) cout << #x << " -> " << x << endl;
#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL);
#define FILE   freopen("input.txt", "r", stdin);  freopen("out.txt", "w", stdout);
using namespace std;
const int N = 300010;
ll t, x;
int solve() {
	cin>>x;
	cout<<(x^1)<<endl;
	return 0;
}
int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	return solve();
}

Measured memory_bytes: 3596
#include <iostream>
#include <cmath>
#include <string>
using namespace std;
int main()
{
  string S;
  int s, min = 1000;
  cin >> S;
  for(int i = 0; i < (int)(S.length()) - 2; i++) {
    s = (int(S[i]) - 48) * 100 + (int(S[i + 1]) - 48) * 10 + (int(S[i + 2]) -48);
    if(min > abs(s - 753)) min = abs(s - 753);
  }
  cout << min;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
void alert(vector<int> vec){
  int64_t N = vec.size();
  for(int i=0; i<N-1; i++) cout << vec.at(i) << " ";
  cout << vec.at(N-1) << endl;
}

int main(){
  int64_t X, Y, A, B, C;
  cin >> X >> Y >> A >> B >> C;
  vector<int64_t> p(A), q(B), r(C);
  for(int64_t i=0; i<A; i++) cin >> p.at(i);
  for(int64_t i=0; i<B; i++) cin >> q.at(i);
  for(int64_t i=0; i<C; i++) cin >> r.at(i);
  vector<pair<int64_t,int>> good;
  for(int64_t i=0; i<A; i++) good.push_back(make_pair(p.at(i),0));
  for(int64_t i=0; i<B; i++) good.push_back(make_pair(q.at(i),1));
  for(int64_t i=0; i<C; i++) good.push_back(make_pair(r.at(i),2));
  sort(good.begin(),good.end());
  reverse(good.begin(),good.end());
  int64_t ans = 0;
  int64_t i = 0;
  pair<int64_t, int> pa(p.at(0),0);
  int64_t Z = 0;
  while((X>0 || Y>0) && X+Y-Z>0 && i<A+B+C){
    pa = good.at(i);
    if(X>0){
      if(Y>0){//red&green
        if(pa.second==0) X--;
        else if(pa.second==1) Y--;
        else Z++;
        ans += pa.first;
      }
      else{//red
        if(pa.second==0) X--;
        else if(pa.second==1){
          i++;
          continue;
        }
        else Z++;
        ans += pa.first;
      }
    }
    else{//green
      if(pa.second==0){
        i++;
        continue;
      }
      else if(pa.second==1) Y--;
      else Z++;
      ans += pa.first;
    }
    i++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 12908
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = a; i < b; i++)
#define Rep(i, a, b) for(int i = a; i <= b; i++)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define _GLIBCXX_DEBUG
#define Vl vector<ll>
#define Vs vector<string>
#define Vp vector<pair<ll, ll>>
#define P pair<ll, ll>
using ll = long long;
#define ALL(v) (v).begin(),(v).end()
#define endl "\n"
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define co(x) cout << x << endl
#define coel cout << endl
#define pb push_back
#define sz(v) ((ll)(v).size())
using namespace std;  
const double pi = acos(-1.0);
const ll MOD = 1e9 + 7;
const ll INF = 1LL << 60;
#define pp pair<ll, pair<ll, ll>> 
#define fi first
#define se second

void print(Vl vec){
    rep(i, 0, sz(vec)){
        if(i) cout << " ";
        cout << vec[i];
    }
    coel;
}

////////////////////////////////////////////////////////

int main() {
    ll n; cin >> n;
    Vl c(n-1), s(n-1), f(n-1);
    rep(i, 0, n-1){
        cin >> c[i] >> s[i] >> f[i];
    }
    Vl ans;
    rep(i, 0, n){
        ll t = 0;
        rep(j, i, n-1){
            // if(i == 0) cout << t << endl;
            if(t <= s[j]) t = s[j];
            else if(t%f[j] == 0){}
            else t = t + f[j] - t%f[j];
            t += c[j];
        }
        ans.push_back(t);
    }
    rep(i, 0, sz(ans)) co(ans[i]);

    return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<climits>
#include<iostream>
#include<string>
#include<stack>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<numeric>

#define rep(n) for(int i=0;i<n;i++)
#define repp(j, n) for(int j=0;j<n;j++)
#define reppp(i, m, n) for(int i=m;i<=n;i++)
#define all(c) c.begin(), c.end()
#define rall(c) c.rbegin(), c.rend()
#define MOD 1000000007
#define MAX 1000000001
#define INF 1410065408
#define EPS 1e-9
#define DEBUG 0
#define ll long long
#define Pll pair<ll, ll>
#define Pii pair<int, int>
 
using namespace std;
struct edge{int from, to; ll cost;};

vector< vector<ll> > product(vector< vector<ll> > A, vector< vector<ll> > B, ll height, ll width, ll n, int m){
	
	vector< vector<ll> > C(height, vector<ll>(width, 0));
	
	rep(height){
		repp(j, width){
			repp(k, n){
				C[i][j] += A[i][k] * B[k][j];
			}
            C[i][j] %= m;
		}
	}
	
	return C;
}

signed main(){
    int n,m,t;
    ll a,b,c;
    vector< vector<ll> > ans;
    while(true){
        scanf("%d %d %lld %lld %lld %d", &n, &m, &a, &b, &c, &t);
        if(n == 0) break;

        vector< vector<ll> > s(n, vector<ll>(1));
        rep(n) scanf("%lld", &s[i][0]);

        vector< vector<ll> > A(n, vector<ll>(n, 0));
        rep(n){
            if(i > 0) A[i][i-1] = a;
            A[i][i] = b;
            if(i < n-1) A[i][i+1] = c;
        }

        vector< vector<ll> > B(n, vector<ll>(n, 0));
        rep(n) B[i][i] = 1;
        while(t){
            if(t & 1){
                B = product(B, A, n, n, n, m);
            }
            A = product(A, A, n, n, n, m);
            t = t >> 1;
        }

        vector< vector<ll> > C = product(B, s, n, 1, n, m);
        rep(n-1) printf("%lld ", C[i][0]);
        printf("%lld\n", C[n-1][0]);
    }


}

Measured memory_bytes: 3368
import java.util.*;


public class Main {
    public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		int sum = 0;
		int list[] = new int[n];
		for (int i = 0; i < n; i++) {
		    list[i] = sc.nextInt();
		}
		Arrays.sort(list);
		
		for (int i =0; i < k; i++) {
		    sum += list[i];
		}
		System.out.println(sum);
    }
}


Measured memory_bytes: 38808
#include <bits/stdc++.h>
using namespace std;

int main()
{
    string n;
    cin >> n;
    if (n[0] == n[1] && n[1] == n[2]) {
        cout << "Yes" << endl;
    } else if (n[1] == n[2] && n[2] == n[3]) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
nums = []
loop do
    num = gets.split(" ")
    if num[0] == "0" && num[1] == "0"; break; end
    nums << num
end
(0...nums.size).each do |i|
    if nums[i][1].to_i < nums[i][0].to_i
        print nums[i][1], " ", nums[i][0], "\n"
    else
        print nums[i][0], " ", nums[i][1], "\n"
    end
end


Measured memory_bytes: 6868
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>;
template <class T>
using V = vector<T>;
template <class T>
using VV = V<V<T>>;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i, n) rep2(i, 0, n)
#define rep2(i, m, n) for (int i = m; i < (n); i++)
#define ALL(c) (c).begin(), (c).end()

constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }

template <class T, class U>
void chmin(T& t, const U& u) {
    if (t > u) t = u;
}
template <class T, class U>
void chmax(T& t, const U& u) {
    if (t < u) t = u;
}

template <class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
    os << "(" << p.first << "," << p.second << ")";
    return os;
}

template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    os << "{";
    rep(i, v.size()) {
        if (i) os << ",";
        os << v[i];
    }
    os << "}";
    return os;
}

#ifdef LOCAL
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << " " << H;
    debug_out(T...);
}
#define debug(...) \
    cerr << __LINE__ << " [" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define dump(x) cerr << __LINE__ << " " << #x << " = " << (x) << endl
#else
#define debug(...) (void(0))
#define dump(x) (void(0))
#endif

string norm(string s) {
    string t;
    for (char c : s) {
        if (c == 'R') {
            t.pb(c);
        } else {
            if (t.size() && t.back() == c) {
                t.pop_back();
            } else {
                t.pb(c);
            }
        }
    }
    return t;
}

int N;
ll ans[550000];
ll pre[15], cur[15];
ll p3[15];

void calc() {
    ll a = 0, b = 0;
    rep(i, N) {
        a += pre[i] * p3[i];
        b += cur[i] * p3[i];
    }
    ans[a] = b;
}

void solve(int p, string T) {
    if (p == N) {
        calc();
        return;
    }
    rep(c, 3) {
        pre[p] = c;
        string nx;
        int x = c;
        for (auto t : T) {
            if (t == 'S') {
                nx.pb(t);
                if (x != 0) {
                    x = 3 - x;
                }
            } else {
                ++x;
                if (x == 3) {
                    x = 0;
                    nx.pb(t);
                }
            }
        }
        cur[p] = x;
        solve(p + 1, norm(nx));
    }
}

int main() {
    cin >> N;
    string T;
    cin >> T;

    p3[0] = 1;
    rep(i, N) { p3[i + 1] = p3[i] * 3; }
    solve(0, norm(T));
    rep(i, p3[N]) cout << ans[i] << (i == p3[N] - 1 ? '\n' : ' ');

    return 0;
}

Measured memory_bytes: 8780
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
#include<queue>
#include<stack>
#include<math.h>
#include<map>
typedef long long int ll;
using namespace std;
#define maxn 0x3f3f3f3f


int main()
{
    int a,b,c;
    scanf("%d%d%d",&a,&b,&c);
    printf("%d %d %d\n",c,a,b);
}



Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while (true) {
            String[] lines = br.readLine().split(" ");
            int n = Integer.parseInt(lines[0]);
            int x = Integer.parseInt(lines[1]);
            if (n == 0 && x == 0) {
                break;
            }
            int count = 0;
            for (int i = 1; i < n - 1; i++) {
                if (i * 3 + 2 > x) {
                    break;
                }
                for (int j = i + 1; j < n; j++) {
                    if (i + j + j + 1 > x) {
                        break;
                    }
                    for (int k = x - i - j; k >= j + 1; k--) {
                        if (k > n) {
                            continue;
                        }
                        if (i + j + k == x) {
                            count++;
                            break;
                        }
                    }
                }
            }
            System.out.println(count);
        }
    }
}

Measured memory_bytes: 25304
#include <stdio.h>

int main()
{
	int n;

	scanf("%d", &n);

	if (n >= 1 && n <= 999) {
		printf("ABC\n");
	} else if (n >= 1000 && n <= 1999) {
		printf("ABD\n");
	}
	
	return 0;
}


Measured memory_bytes: 128
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    input()
    A = read_list()
    if 0 in A:
        print(0)
        return

    res = 1
    for a in A:
        res *= a
        if res > 10 ** 18:
            print(-1)
            return 
    print(res)


if __name__ == "__main__":
    main()



Measured memory_bytes: 22904
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define fi first
#define se second
typedef pair<ll,ll> P;
using VP = vector<P>; using VVP = vector<VP>;
using VI = vector<ll>; using VVI = vector<VI>; using VVVI = vector<VVI>;
const int inf=1e9+7;
const ll INF=1LL<<58;
const ll mod=1e9+7;


int main(){
  int i,j;
  int n;
  cin>>n;
  for(i=1;i<=50000;i++){
    if(n==(i*108)/100){
      cout<<i<<endl;
      return 0;
    }
  }
  cout<<":("<<endl;

  
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;

int main(){
    string s;
    cin >> s;
    int t = s.size();
    int zeroc = 0,onec = 0;
    int sum = 0;
    for(int i = 0; i < t; i++){
        if(s[i] == '0')
        zeroc++;
        else if(s[i] == '1')
        onec++;
        if(onec != 0 && zeroc != 0){
            zeroc--;
            onec--;
            sum += 2;
        }
    }
    cout << sum <<endl;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = (int)(a); i <= (int)(n); ++i)
#define rrep(i, a, n) for (int i = (int)(a); i >= (int)(n); --i)
#define debug(x) cerr << #x << " = " << x << "\n"
#define debugv(x) \
  rep(f, 0, (x.size() - 1)) cerr << x[f] << (f == (x.size() - 1) ? "\n" : " ")
#define all(x) x.begin(), x.end()
#define int long long
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int MX = 1e5 + 5, INF = 5 << 28, MOD = 1e9 + 7;

int N, M, K;
vi A, B;
string S, T;

void input() {
  int x, y, z;
  cin >> N;
  A.resize(N);
  rep(i, 0, N - 1) { cin >> A[i]; };
}
void solve() {
  int ans = 0;
  for (auto x : A) ans += x;

  sort(all(A));
  for (int i = 0; i < N; ++i) {
    if (ans % 10) break;
    if ((ans - A[i]) % 10 != 0) {
      ans -= A[i];
      break;
    }
  }
  cout << (ans % 10 ? ans : 0LL) << endl;
  ;
  ;
}
signed main() {
  input();
  solve();
  return 0;
}

Measured memory_bytes: 256
n,k = map(int,raw_input().split())
boats = [map(int,raw_input().split()) for i in range(k)]
r = input()
hate = [map(int,raw_input().split()) for i in range(r)]
blue = []
for i,j in hate:
	for boat in boats:
		if i in boat[1:] and j in boat[1:]:
			if i not in blue: blue.append(i)
			if j not in blue: blue.append(j)
print len(blue)

Measured memory_bytes: 4332
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <limits>

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }

//math
//-------------------------------------------
template<class T> inline T sqr(T x) { return x * x; }

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define EXISTch(s,c) ((((s).find_first_of(c)) != std::string::npos)? 1 : 0)//cがあれば1 if(1)
#define SORT(c) sort((c).begin(),(c).end())

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int INF = (int)1000000007;
const LL MOD = (LL)1000000007;//10^9+7
const LL INF2 = (LL)100000000000000000;//10^18

int main() {

	string s; cin >> s;
	int l = s.size();

	int c0 = 0;
	int c1 = 0;

	if (s[0] == '1') {
		c1++;
	}
	else {
		c0++;
	}

	for (int i = 1; i < s.size(); i++) {
		
		if (c0 > 0) {
			if (s[i] == '0') {
				c0++;
			}
			else {
				c0--;
			}
		}
		else if (c0 == 0 && c1 == 0) {
			if (s[i] == '0') {
				c0++;
			}
			else {
				c1++;
			}
		}

		else {
			if (s[i] == '1') {
				c1++;
			}
			else {
				c1--;
			}
		}
		
	}

	cout << l - max(c0, c1) << endl;

	return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < (n); i++)
#define REPR(i, n) for(int i = (n); i >= 0; i--)
#define FOR(i, m, n) for(int i = (m); i < (n); i++)
#define INF 1e9
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << #x << ": " << x << endl;

using namespace std;
typedef long long ll;

signed main() {
  int a, b, c;
  cin >> a >> b >> c;
  if(a + b + c >= 22) {
    cout << "bust" << endl;
  } else {
    cout << "win" << endl;
  }
  return 0;
}


Measured memory_bytes: 256
using System;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Collections.Generic;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;
using static System.Math;
using Debug = System.Diagnostics.Debug;
using MethodImplOptions = System.Runtime.CompilerServices.MethodImplOptions;
using MethodImplAttribute = System.Runtime.CompilerServices.MethodImplAttribute;

static class P
{
    static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        var h = Console.ReadLine().Split().Select(int.Parse).ToArray();
        int last = -1;
        for (int i = 0; i < n; i++)
        {
            if (last > h[i])
            {
                h[i]++;
                if (last > h[i])
                {
                    Console.WriteLine("No");
                    return;
                }
            }
            last = h[i];
        }
        Console.WriteLine("Yes");
    }


    static readonly TextReader In = Console.In;
    static int NextInt
    {
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        get
        {
            int res = 0;
            int next = In.Read();
            int rev = 1;
            while (45 > next || next > 57) next = In.Read();
            if (next == 45) { next = In.Read(); rev = -1; }
            while (48 <= next && next <= 57)
            {
                res = res * 10 + next - 48;
                next = In.Read();
            }
            return res * rev;
        }
    }
}


Measured memory_bytes: 28124
#include <bits/stdc++.h>
#define fin ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
#define ll long long
ll dp[1<<21];
int mod=1e9 +7;
#define MAX 1e18+5;
int main()
{
  fin;
  int n;
  cin>>n;
  int a[n][n];
  for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
      cin>>a[i][j];
  memset(dp,0,sizeof(dp));
  dp[0]=1;
  for(int mask=0;mask<(1<<n)-1;mask++)
  {
    int x=__builtin_popcount(mask);
    for(int y=0;y<n;y++)
    {
      if(a[x][y] && !(mask&(1<<y)))
      {
        int m2=mask|(1<<y);
        dp[m2]+=dp[mask];
        dp[m2]%=mod;
      }
    }
  }
  cout<<dp[(1<<n)-1];
}


Measured memory_bytes: 16640
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

#[allow(dead_code)]
fn practice_1() {
    input! {
    n: i32,
    m: [i32; 2],
    s: chars,
    }
    let s: Vec<char> = s;
    let s: String = s.into_iter().collect();

    println!("{} {}", n + m[0] + m[1], s);
}

#[allow(dead_code)]
fn abc086_a() {
    input! {
    n: [i32; 2],
    }
    let prod: i32 = n[0] * n[1];
    let res = if prod % 2 == 0 {
        "Even"
    } else {
        "Odd"
    };
    println!("{}", res)
}

#[allow(dead_code)]
fn abc081_a() {
    input! {
    s: chars,
    }
    let s: Vec<char> = s;
    let res: u32 = s.into_iter().map(|n| {
        n.to_digit(10).unwrap()
    }).sum();

    println!("{}", res)
}

#[allow(dead_code)]
fn abc081_b() {
    input! {
    n: i32,
    arr: [i32; n],
    }
    let mut arr: Vec<i32> = arr;
    let mut cnt = 0;

    loop {
        let is_end: bool = arr.to_vec().into_iter().any(|v| (v % 2) == 1);
        if is_end { break; }
        arr = arr.to_vec().into_iter()
            .map(|v| v / 2)
            .collect();
        cnt = cnt + 1;
    }

    println!("{}", cnt)
}

#[allow(dead_code)]
fn abc087_b() {
    input! {
    n_500: i32,
    n_100: i32,
    n_50: i32,
    total: i32,
    }

    let n_500: i32 = n_500;
    let n_100: i32 = n_100;
    let n_50: i32 = n_50;
    let total: i32 = total;
    let mut cnt = 0;

    for i in 0..n_500 + 1 {
        for j in 0..n_100 + 1 {
            for k in 0..n_50 + 1 {
                let total_tried = i * 500 + j * 100 + k * 50;
                if total_tried == total {
//                    println!("{}, {}, {}", i, j, k);
                    cnt += 1;
                }
            }
        }
    }

    println!("{}", cnt)
}


fn main() {
    abc087_b()
}



Measured memory_bytes: 4352
using System;
using System.Linq;
using System.Collections.Generic;

namespace AtCoder.Contests.ABC164
{
    /// <summary>
    /// 
    /// </summary>
    static class C
    {
        static void Main(string[] args)
        {
            var n = NextInt();

            var hashSet = new HashSet<string>();
            for (int i = 0; i < n; i++)
            {
                hashSet.Add(Next());
            }

            Console.WriteLine(hashSet.Count());
        }

        #region Console
        static int _index = 0;
        static string[] _buffer;

        static string Next()
        {
            if (_buffer == null || _index >= _buffer.Length)
            {
                _buffer = Console.ReadLine().Split();
                _index = 0;
            }

            return _buffer[_index++];
        }
        static int NextInt()
        {
            return int.Parse(Next());
        }
        static long NextLong()
        {
            return long.Parse(Next());
        }
        static int ReadInt()
        {
            return int.Parse(Console.ReadLine());
        }
        static long ReadLong()
        {
            return long.Parse(Console.ReadLine());
        }
        static int[] ReadIntArray()
        {
            return Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
        }
        static int[] ReadIntArray(int n)
        {
            var a = new int[n];
            for (int i = 0; i < n; i++)
            {
                a[i] = ReadInt();
            }
            return a;
        }
        static long[] ReadLongArray()
        {
            return Console.ReadLine().Split(' ').Select(long.Parse).ToArray();
        }
        static long[] ReadLongArray(int n)
        {
            var a = new long[n];
            for (int i = 0; i < n; i++)
            {
                a[i] = ReadLong();
            }
            return a;
        }
        static List<T> ReadObjects<T>(int n, Func<int[], T> creator)
        {
            var l = new List<T>(n);

            for (int i = 0; i < n; i++)
            {
                var a = ReadIntArray();
                l.Add(creator(a));
            }

            return l;
        }

        static int[,] ReadMatrix(int n, int m)
        {
            var r = new int[n, m];
            for (int i = 0; i < n; i++)
            {
                var a = ReadIntArray();
                for (int j = 0; j < m; j++)
                {
                    r[i, j] = a[j];
                }
            }
            return r;
        }
        #endregion
    }
}


Measured memory_bytes: 51204
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;
typedef vector<ll> vll;
typedef vector<ld> vld;
typedef vector<pll> vpl;

#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define FI first
#define SE second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define REP1(i,n) for(int i=1;i<((int)n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define PB push_back
#define EB emplace_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL

const int inf = 1e9;
const ll linf = 1LL << 50;
const double eps = 1e-10;
const int MOD = 1e9 + 7;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  ll a,b,c;
  cin>>a>>b>>c;

  ll d=c-(a+b);

  ll l=4*a*b;
  ll r=pow(c-(a+b), 2);
  if(d>0 && l<d*d)
    cout<<"Yes"<<endl;
  else
    cout<<"No"<<endl;


}



Measured memory_bytes: 256
#include<iostream>
#include<map>
#include<string>
using namespace std;

int main(){
    int n;
    cin >> n;
    string str;
    map<string, int> get;
    for(int i=0; i<n; i++){
        cin >> str;
        if(get.count(str)) get.insert(make_pair(str, 1));
        else get[str]++;
    }

    cout << get.size() << endl;
}

Measured memory_bytes: 19100
#include <stdio.h>

int main(void)
{
	int m, n;
	int i, j;
	int count;
	
	
	while (1){
		scanf("%d", &m);
		if (m == 0){
			break;
		}
		scanf("%d", &n);
		
		count = 0;
		for (i = m; i <= n; i++){
			j = i;
			while (1){
				if (j % 2 == 0){
					j /= 2;
				}
				else if (j % 3 == 0){
					j /= 3;
				}
				else if (j % 5 == 0){
					j /= 5;
				}
				else if (j == 1){
					count++;
					break;
				}
				else {
					break;
				}
			}
		}
		
		printf("%d\n", count);
	}
	
	return (0);
}

Measured memory_bytes: 404