akhauriyash/Code-Regression huggingface dataset:
#include "iostream"
#include "algorithm"
#include "vector"
#include "string"
#include "cmath"
typedef long long ll;
using namespace std;

int main(int argc, char const *argv[]) {
  ll NN, MM;


  std::cin >> NN >> MM;

  std::vector<ll> A(NN);
  for (size_t i = 0; i < NN; i++) {
    std::cin >> A[i];
  }

  // for (size_t i = 0; i < NN; i++) {
  //   std::cout << A[i] << '\n';
  // }
  std::sort (A.begin(), A.end());

  // for (size_t i = 0; i < NN; i++) {
  //   std::cout << A[i] << '\n';
  // }

  // ll B[MM], C[MM];
  //
  // for (size_t i = 0; i < MM; i++) {
  //   std::cin >> B[i]>>C[i];
  // }

  std::vector<pair<ll, ll>> CB(MM);

  // std::cout << "------------------" << '\n';

  for (ll i = 0; i < MM; i++) {
    ll B, C;
    std::cin >> B>>C;
    CB[i] = make_pair(C, B);
    // CB[i] = make_pair(C[i], B[i]);
  }
  // std::cout << "------------------" << '\n';


  // for (ll i = 0; i < MM; i++) {
  //   std::cout << CB[i].first << " "<< CB[i].second << '\n';
  // }
  // sort(ALL(CB));
  sort(CB.begin(), CB.end());

  // std::cout << "------------------" << '\n';
  // std::cout << "A------" << '\n';
  // for (size_t i = 0; i < NN; i++) {
  //   std::cout << A[i] << '\n';
  // }
  // std::cout << "C B------" << '\n';
  //
  // for (ll i = 0; i < MM; i++) {
  //   std::cout << CB[i].first << " "<< CB[i].second << '\n';
  // }

  // replace ---------------------------
  // std::cout << "replacing--------" << '\n';
  ll A_now = 0;
  ll break_flag = 0;

  for (ll i = 0; i < MM; i++) {
    ll B_now = MM - i - 1;
    if (A[A_now] > CB[B_now].first ) {
      break_flag = 1;
    }
    if (break_flag == 1) {
      break;
    }

    for (size_t j = 0; j < CB[B_now].second; j++) {
      A[A_now] = CB[B_now].first;
      A_now++;

      if (A[A_now] > CB[B_now].first ) {
        break_flag = 1;
      }
      if (break_flag == 1) {
        break;
      }
    }


    if (break_flag == 1) {
      break;
    }
  }

  // test ---------------------------

  // for (size_t i = 0; i < NN; i++) {
  //   std::cout << A[i] << '\n';
  // }

  ll ans = 0;
  for (size_t i = 0; i < NN; i++) {
    ans += A[i];
  }
  std::cout << ans << '\n';


  return 0;
}


Measured memory_bytes: 2560
#include<bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
using LL = long long;
const LL LINF = 1e18;
using namespace std;
#define COUT(v) cout<<(v)<<endl
#define CIN(n)  int(n);cin >> (n)
#define SCIN(n) string(n);cin >> (n)
#define YES(n) cout<<((n)? "YES" : "NO")<<endl
#define Yes(n) cout<<((n)? "Yes" : "No")<<endl
#define POSSIBLE(n) cout << ((n) ? "POSSIBLE" : "IMPOSSIBLE"  ) << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible"  ) <<endl

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)

#define FOREACH(x,a) for(auto& (x) : (a) )

#define ALL(obj) (obj).begin(),(obj).end()

#define P pair<int,int>
#define I vector<int>
#define S set<int>
#define pb(v) push_back(v)
#define V vector
#define rt return
#define rmsame(a) sort(ALL(a)),a.erase(unique(ALL(a)), a.end())

typedef string::const_iterator State;
class PalseError {};
class Edge{
public:
    int from,to,value;
    Edge(int a,int b,int c){
        from = a;
        to = b;
        value = c;
    }
    Edge(int a,int b){
        from = a;
        to = b;
    }
};
int main(){
    CIN(N);
    if(N%2==0){
        COUT(N);
    }else{
        COUT(N*2);
    }
    return 0;
}


Measured memory_bytes: 256
N, M = map(int, raw_input().split())
A = [False]*N
C = [0]*N
for i in range(M):
  p, S = raw_input().split()
  p = int(p)-1
  if S=="AC":
    A[p] = True
  else:
    if not A[p]:
      C[p] += 1
print sum(A), sum(C[i] for i in range(N) if A[i])


Measured memory_bytes: 7336
#include <algorithm>
#include <climits>
#include <iostream>
#include <string>
#include <utility>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <cmath>

using namespace std;
using ll = long long int;

template <class T> ostream &operator<<(ostream &os, vector<T> &v) {
  for (auto i = v.begin(); i != v.end(); i++) {
    os << *i << " ";
  }
  return os;
}


void solve(long long N, std::vector<long long> a){
  ll cnt = 1;
  for(int i=0; i<N; i++) {
    if(a[i]==cnt)
      cnt++;
  }
  //std::cout << cnt << std::endl;
  if(cnt==1)
    std::cout << -1 << std::endl;
  else
    std::cout << N-(cnt-1) << std::endl;
}

int main(){
  long long N;
  scanf("%lld",&N);
  std::vector<long long> a(N);
  for(int i = 0 ; i < N ; i++){
    scanf("%lld",&a[i]);
  }
  solve(N, std::move(a));
  return 0;
}



Measured memory_bytes: 1792
# -*- coding: utf-8 -*-

"""
参考：https://pitsbuffersolution.com/compro/atcoder/arc089d.php
　　　http://tutuz.hateblo.jp/entry/2018/06/20/212752
　　　https://paiza.hatenablog.com/entry/2014/05/28/%E3%82%82%E3%81%97%E5%A5%B3%E5%AD%90%E5%A4%A7%E7%94%9F%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9E%E3%81%AB%E3%80%8E%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%80%8F%E3%82%92%E5%9B%B3
　　　http://www.learning-algorithms.com/entry/2018/01/31/144519
　　　https://img.atcoder.jp/arc089/editorial.pdf
・2次元累積和
・0-indexedのまま行くか1-indexedにするか人によって色々で、
　それぞれに考慮する点があると思った。
・定数倍高速化のためループまとめて(4K^2)*3回を1回にしたから、
　5200万がO((4K)^2+(2K)^2)=2000万くらいになって結構速くなったはず。
　…と思ったらメモリがオーバーしたから余計な配列減らした。
"""

import sys
def input(): return sys.stdin.readline().strip()

N, K = map(int, input().split())

# ここは循環するK*2まで作る
B = [[0] * (K*2+1) for i in range(K*2+1)]
for i in range(N):
    x, y, c = input().split()
    x, y = int(x), int(y)
    # 白に塗る条件はxかyにKずらして黒の条件にする(これで2色考えなくていい)
    if c == 'W':
        y += K
    # 循環するのでmod K*2でやる
    # 累積和でひとつ前を見に行くので、1-indexedにする
    B[x%(K*2)+1][y%(K*2)+1] += 1

# ここはK*2の正方形を右下まで動かすので、K*4まで作っておく
sm = [[0] * (K*4+1) for i in range(K*4+1)]
# 2次元累積和を取る
# 1-indexedなので、気にせず1からループすればいい
for i in range(1, K*4+1):
    for j in range(1, K*4+1):
        # K*2からはみ出る範囲も正しく累積和を出すため、K*2までの値を循環させる
        # 1-indexedにしているため、ここの加減がややこしい
        sm[i][j] = B[(i-1)%(K*2)+1][(j-1)%(K*2)+1]
        # 縦横の累積和を同時に集めていく
        sm[i][j] += sm[i][j-1] + sm[i-1][j] - sm[i-1][j-1]

# 2次元累積和に必要な4点の加減を行う
def get_sum(x1, y1, x2, y2, sm):
    # 1-indexedなので、x, yがマイナスの値になる考慮は必要ない
    res = sm[x2][y2] - sm[x1-1][y2] - sm[x2][y1-1] + sm[x1-1][y1-1]
    return res

ans = 0
for i in range(1, K*2+1):
    for j in range(1, K*2+1):
        # 1つ目の黒い正方形
        tmp = get_sum(i, j, i+K-1, j+K-1, sm)
        # 2つ目の黒い正方形
        tmp += get_sum(i+K, j+K, i+K*2-1, j+K*2-1, sm)
        ans = max(tmp, ans)
print(ans)


Measured memory_bytes: 197596
#include <iostream>
#include <stdio.h>
#include <vector>
#include <cstring>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <utility>
#include <queue>
#include <deque>
#include <stack>
#include <time.h>
#include <stdlib.h>
#include <bitset>
#include <algorithm>

#include <chrono>

#define INF 1e9
#define LL_INF 1e18

#define fst first
#define snd second
#define pb push_back
#define SZ(x) ((int)(x.size()))

#define MOD1 998244353
#define MOD2 666013
#define P1 255
#define P2 2059

using namespace std;

typedef long long int ll;

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

#define nmax (1 << 21) + 5
#define MOD (1e9) + 7 

int n;
int dp[22][nmax];
vector <int> vc[25];

void add_self(int& a, int b)
{
    a += b;
    
    if (a >= MOD) a -= MOD;
}

int main()
{
    scanf("%d", &n);

    dp[0][0] = 1;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {

            int x;

            scanf("%d", &x);
            
            if (x == 1) vc[i].pb(j);
        }

    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < (1 << n); j++)
            if (dp[i - 1][j] > 0) {

                for (int l = 0; l < SZ(vc[i]); l++)
                {
                    int k = vc[i][l] - 1;

                    if (((j >> k) & 1) == 0)
                        add_self(dp[i][j + (1 << k)], dp[i - 1][j]);
                }
            }
    }

    printf("%d", dp[n][(1 << n) - 1]);

    // IMPORTANT!!!!!
    // Are you missing something????
    // check limits, int or ll

    return 0;
}

Measured memory_bytes: 162048
from collections import deque

H, W = map(int, input().split())
cy, cx = map(int, input().split())
sy, sx = map(int, input().split())
tiles = [list(input()) for _ in range(H)]

# initialization
INF = 10**4
arrived = [[INF for _ in range(W)] for __ in range(H)]
paths = deque()
warps = deque()
dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]
moves = [-2, -1, 0, 1, 2]
arrived[cy-1][cx-1] = 0
paths.append([cx-1, cy-1])
count = 0

# BFS
while(len(paths) > 0):
  while(len(paths) > 0):
    nx, ny = paths.popleft()
    for i in range(4):
      if 0 <= nx+dx[i] < W and 0 <= ny+dy[i] < H and arrived[ny+dy[i]][nx+dx[i]] > count and tiles[ny+dy[i]][nx+dx[i]] == '.':
        paths.append([nx+dx[i], ny+dy[i]])
        arrived[ny+dy[i]][nx+dx[i]] = count
    for x in moves:
      for y in moves:
        if 0 <= nx+x < W and 0 <= ny+y < H and arrived[ny+y][nx+x] == INF and tiles[ny+y][nx+x] == '.':
          warps.append([nx+x, ny+y])
  count += 1
  while(len(warps) > 0):
    nx, ny = warps.popleft()
    if arrived[ny][nx] == INF:
      arrived[ny][nx] = count
      paths.append([nx, ny])

if arrived[sy-1][sx-1] != INF:
  print(arrived[sy-1][sx-1])
else:
  print(-1)

Measured memory_bytes: 167872
s = input()
atgc = ("A","T","G","C")
maxlen = 0
for i in range(len(s)):
	cnt = 0
	if s[i] in atgc:
		cnt += 1
		for j in range(i+1,len(s)):
			if s[j] in atgc:
				cnt += 1
			else:
				break
	if cnt > maxlen:
		maxlen = cnt
print(maxlen)

Measured memory_bytes: 3060
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <functional>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

#define fst first
#define scd second
#define PB push_back
#define MP make_pair
#define rep(i,x) for(int i=0;i<(x);++i)
#define rep1(i,x) for(int i=1;i<=(x);++i)
#define rrep(i,x) for(int i=(x)-1;i>=0;--i)
#define rrep1(i,x) for(int i=(x);i>=1;--i)
#define FOR(i,a,x) for(int i=(a);i<(x);++i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()

#define omajinai ios::sync_with_stdio(false);cin.tie(0)

template<typename T>bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<typename T>bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<typename T>T get(){T a;cin>>a;return a;}
template<typename T>T rev(T a){reverse(all(a));return a;}
template<typename T>istream&operator>>(istream&is,vector<T>&vec){rep(i,vec.size())is>>vec[i];return is;}
template<typename T>vector<T>&sort(vector<T>&a){sort(all(a));return a;}

const int inf = 1e9;
const ll linf = 3e18;
const double eps = 1e-9;

int C[300010];

signed main()
{
    int N, Q; cin >> N >> Q;

    rep(i, N) {
        int c; cin >> c;
        C[c] = c;
    }

    rep1(i, 300000) {
        chmax(C[i], C[i - 1]);
    }

    rep(i, Q) {
        int q; cin >> q;

        int ma = 0;

        for (int j = q - 1; j <= 300000; j += q) {
            chmax(ma, C[j] % q);
        }

        cout << ma << endl;
    }
}

Measured memory_bytes: 2332
#include <iostream>
#include <climits>
#include <cmath>
using namespace std;
int main() {
  int A, B, C, X, Y, min = INT_MAX;
  cin >> A >> B >> C >> X >> Y;
  for (int i = 0; i < 100001; i++) {
    int v = 2 * C * i + max(0, X - i) * A + max(0, Y - i) * B;
    if (v < min) min = v;
  }
  cout << min << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <stack>
#include <list>
#include <utility>
#include <vector>
#include <set>
#include <algorithm>
#include <cmath>
#include <climits>
#include <map>
#include <unordered_map>
#include <string.h>
#include<iomanip>
#include <iterator>
#include <locale>

#define all(a) a.begin(),a.end()
#define VV(T) vector<vector< T > >
#define rep(i,N) for(int i = 0; i <N; i++)
#define repsg(i,s,g) for(int i = s; i <g; i++)
#define name(x) #x
using namespace std;

const int INF = INT_MAX;
const long long INFL =LONG_LONG_MAX;
const double PI = atan(1)*4;
const int MOD = pow(10,9)+7;
int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

typedef long long ll,LL;
typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;
typedef pair<int,int> pii;
typedef pair<LL, LL> pLL;


// vector入力
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
    for(T& x: vec) is >> x;
    return is;
}
// vector出力
template<typename T>
ostream& operator << (ostream& os, vector<T>& vec){
    for(int i=0; i<vec.size(); i++){
        os << vec[i] << ( i+1 == vec.size() ? "" : " " );
    }
    return os;
}


int main() {
    ll x,y;cin>>x>>y;
    ll ans;
    
    if(x>=y){
        ans = INFL;
        ans = min(ans, 2+abs(abs(x)-abs(y)));
        ans = min(ans, 1 + abs(y+x));
    }else{
        ans = y-x;
        
        ans = min(ans,1+abs(y+x));
        
        ans = min(ans,abs(abs(y)-abs(x))+1);
        
        
    }
    cout<<ans<<endl;
    
    return 0;
}








Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	ll u,v,a,b,c;
	cin>>u>>v>>a>>b>>c;
	ll p[a],q[b],r[c];
	for(ll i=0;i<a;i++)
		cin>>p[i];
	for(ll i=0;i<b;i++)
		cin>>q[i];
	for(ll i=0;i<c;i++)
		cin>>r[i];
	sort(p,p+a,greater<ll> ());
	sort(q,q+b,greater<ll> ());
	sort(r,r+c);
	vector<ll> t,t1;
	ll ans = 0;
	for(ll i=0;i<u;i++)
	{
		t.push_back(p[i]);
		ans+=p[i];
	}
	for(ll i=0;i<v;i++)
	{
		t.push_back(q[i]);
		ans+=q[i];
	}
	sort(t.begin(),t.end());
	ll i=0,idx=c-1;
	while(i<t.size() and idx>=0)
	{
		if (t[i]<=r[idx])
		{
			ans+=(r[idx]-t[i]);
			i++;
			idx--;
		}
		else
		{
			break;
		}
	}
	cout<<ans;
}

Measured memory_bytes: 4724
#include <bits/stdc++.h>
#define ll long long 
using namespace std;




int main() {
   #ifndef ONLINE_JUDGE
  freopen("input.txt","r",stdin);
  freopen("output.txt","w",stdout);
  #endif
 ios_base::sync_with_stdio(0);
 cin.tie(0);
 cout.tie(0);
 ll w,h,n; 
 cin>>w>>h>>n;
 ll xa,xb,ya,yb;
 xa=0,xb=w,ya=0,yb=h;

 while(cin>>w>>h>>n){
  if(n==1) xa=max(w,xa);
 if(n==2) xb=min(w,xb);
 if(n==3) ya=max(h,ya);
 if(n==4) yb=min(h,yb);
 }
 ll mb,mo;
 if(xb-xa>0) mb=xb-xa;
 else mb=0;
 if(yb-ya>0) mo=yb-ya;
 else mo=0;
 
 cout<<mb*mo<<endl;

 return 0;
}


Measured memory_bytes: 3564
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <vector>
using ll = long long int;
using namespace std;

int main()
{
    int N;
    cin >> N;
    cout << (N - 1) / 2 << endl;

    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <iterator>
#include <assert.h>
#pragma warning(disable:4996) 
 
typedef long long ll;
#define MIN(a, b) ((a)>(b)? (b): (a))
#define MAX(a, b) ((a)<(b)? (b): (a))
#define LINF 9223300000000000000
#define INF 2140000000
const long long MOD = 1000000007;
//const long long MOD = 998244353;
using namespace std;


int main(int argc, char* argv[])
{
    int a,b,c;
    scanf("%d%d%d", &a, &b, &c);
    if(a+b+c>=22) {
        printf("bust\n");
    }
    else {
        printf("win\n");
    }

    return 0;
}



Measured memory_bytes: 128
//
#include <iostream>
#include <cstdio>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <array>
#include <numeric>
#include <functional>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<utility>
#include<complex>

using namespace std;

#define REP(i,m,n) for(int i=m;i<(n);i++)
#define rep(i,n) REP(i,0,n)
#define ALL(x) (x).begin(),(x).end()

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

const ll inf = INT_MAX;
const double eps = 1e-10;
const double pi = acos(-1.0);
const int di[][2] = {{1,0},{0,1},{-1,0},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}};

int main(){

	int n, k;
	cin >> n >> k;
	int ret = k;
	rep(i,n-1){
		ret *= (k-1);
	}
	printf("%d\n", ret);
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0, max_i = (n); i < max_i; i++)
#define REPI(i, a, b) for (int i = (a), max_i = (b); i < max_i; i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define RALL(obj) (obj).rbegin(), (obj).rend()
#define fi first
#define se second
#define int long long
using namespace std;
using ll = long long;
using II = pair<int, int>; using VII = vector<II>; using VVII = vector<VII>;
using VI = vector<int>; using VVI = vector<VI>; using VVVI = vector<VVI>;
template <class T = int> inline bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template <class T = int> inline bool chmin(T &a, const T &b) { if (a > b) { a = b; return true; } return false; }
template <class T> ostream& operator<<(ostream &s, const vector<T>& d) { int n = d.size(); REP (i, n) s << d[i] << " "; return s; }
template <class T> ostream& operator<<(ostream &s, const vector<vector<T>>& dd) { for (vector<T> d: dd) s << d << endl; return s; }
template <class T, class S> ostream& operator<<(ostream &s, const pair<T, S>& p) { s << "{" << p.first << ", " << p.second << "}"; return s; }
#ifdef _MY_DEBUG
  #define dump(...) cerr << "\t" << #__VA_ARGS__ << " :[" << __LINE__ << ":" << __FUNCTION__ << "]" << endl << "\t", dump_func(__VA_ARGS__);
#else
  #define dump(...)
#endif
void dump_func() { cerr << endl; }
template <class Head, class... Tail> void dump_func(Head&& h, Tail&&... t) { cerr << h << (sizeof...(Tail) == 0 ? "" : ", "), dump_func(forward<Tail>(t)...); }
struct Fast { Fast() { cin.tie(0); ios::sync_with_stdio(false); } } fast;
const int MOD = 1e9 + 7;

signed main() {
  struct Edge {
    int to, c;
  };
  int n; cin >> n;
  vector<vector<Edge>> G(n);
  REP (i, n - 1) {
    int s, t, w; cin >> s >> t >> w;
    G[s].push_back({t, w});
    G[t].push_back({s, w});
  }
  int ans = 0;
  function<int(int, int)> dfs = [&](int v, int p) {
    int ma = 0;
    for (Edge e: G[v]) if (e.to != p) {
      int tmp = dfs(e.to, v) + e.c;
      ans = max(ans, ma + tmp);
      ma = max(ma, tmp);
    }
    return ma;
  };
  dfs(0, -1);
  cout << ans << endl;
}



Measured memory_bytes: 19172
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(n); i++)
using namespace std;
typedef pair<int, int> PII;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
const int INF = numeric_limits<int>::max();
char C[110][110];
int dis[110][110];

void bfs(int x,int y, int row, int col){
    
    int dy[4] = { 1, 0, -1, 0 }, dx[4] = { 0, 1, 0, -1 };//移動4方向のベクトル
    queue<PII> q;//pair型のqueueの定義
    q.emplace(y, x );//スタート地点座標をqueueに代入
    
    while( !q.empty() )
    {
        PII now = q.front();//現在地
        q.pop();//一番上のデータを削除

        //移動4方向をループ
        REP( i, 4 )
        {
            //移動した後の点を(ny,nx)とする
            int ny = now.first + dy[i], nx = now.second + dx[i];

            //移動が可能かの判断と既に訪れた事があるかの判定
            if( 1 <= ny && ny <= row && 1 <= nx && nx <= col && C[ny][nx] != '#' && dis[ny][nx] == 0 )
            {
                q.emplace( ny, nx );//キー(ny),value(nx),次の位置をqueueに入れる
                dis[ny][nx] = dis[now.first][now.second] + 1;//点の距離をnowから+1の距離で確定する  
            }   
        }
    }
    
    
}


int main()
{
    int row{}, col{};//行,列
    int sy{},sx{};//スタート地点の座標(y,x)
    int gy{},gx{};//ゴール地点の座標(y,x)
    int sharp=0;
    cin >> row >> col;
    
    sx=sy=1;
    gx=col;
    gy=row;
    
    fill(dis[0], dis[row], 0);//配列初期化
    //cout<<dis[1][1]<<endl;



    //char C[row+1][col+1];
    REP( i, row )
    {
        REP( j, col )
        {
            cin >> C[i+1][j+1];//座標は1,1から始まるので+1して合わせる
            if(C[i+1][j+1]=='#'){
            sharp++;
                
            }
        }
    }
    
    bfs(sx,sy,row,col);
    int d=dis[gy][gx];
    //cout<<row*col<<endl;
    //cout<<sharp<<endl;
    if(d==0) cout<<-1<<endl;
    else cout<<row*col-sharp-d-1<<endl;
    

   
   // cout << distance[gy][gx] << endl;
    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

const int MAX_N = 1e5 + 15, UNMARKED = 0;
vector <int> graph[MAX_N];
int component[MAX_N];

void dfs(int v, int component_no)
{
    component[v] = component_no;

    for(int i = 0; i < graph[v].size(); i++)
    {
        int child = graph[v][i];

        if(component[child] == UNMARKED)
            dfs(child, component_no);
    }
}

int main()
{
    int n, no_of_edges;
    scanf("%d %d", &n, &no_of_edges);

    vector <int> permutation(n + 1);
    for(int i = 1; i <= n; i++)
        scanf("%d", &permutation[i]);

    for(int i = 1; i <= no_of_edges; i++)
    {
        int u, v;
        scanf("%d %d", &u, &v);

        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    memset(component, UNMARKED, sizeof(component));

    int component_no = 1;

    for(int i = 1; i <= n; i++)
    {
        if(component[i] == UNMARKED)
            dfs(i, component_no++);
    }

    int no_of_inplace_elements = 0;
    for(int i = 1; i <= n; i++)
        no_of_inplace_elements += (i == permutation[i] || component[i] == component[permutation[i]]);

    printf("%d\n", no_of_inplace_elements);
    return 0;
}


Measured memory_bytes: 9472
#include "bits/stdc++.h"
using namespace std;
#define ff first
#define ss second
#define pb push_back
typedef long long ll;
#define db(x) cerr<<__LINE__<<": "<<#x<<" = "<<(x)<<'\n'
const int inf = 1e9+7;
const int N = 1e6+9;

void solve() {
	ll a;
	string b;
	cin>>a>>b;
	string x;
	for(char ch: b) if(ch!='.') {
		x+=ch;
	}
	int p=stoi(x);
	cout<<a*p/100<<endl;
}
int main() {
    ios_base::sync_with_stdio(0);
    int T=1 ,cas=0;
    while(T--) {
    	solve();
    }
    return 0;
}

// ll, reset, 1, bottom

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

int d()
{
    long long x;
    std::cin >> x;
    
    int a = 0;
    int b = 0;
    for(int i = -500; i < 500; i++)
    {
        for(int k = -500; k < 500; k++)
        {
            long long temp = pow(i, 5) - pow(k, 5);
            if(temp == x)
            {
                a = i;
                b = k;
            }
        }
    }
    
    std::cout << a << " " << b << std::endl;
    
    return 0;
}

int main(int argc, const char * argv[])
{
    d();
    return 0;
}

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

const string hands[] = {"Rock", "Fire", "Scissors", "Snake", "Human",
			"Tree", "Wolf", "Sponge", "Paper", "Air",
			"Water", "Dragon", "Devil", "Lightning", "Gun" };
int main(){
  int n;
  while(cin >> n,n){
    vector<int> use(15,0);
    while(n--){
      string s;
      cin >> s;
      for(int i=0;i<15;i++){
	if(s == hands[i])use[i] = 1;
      }
    }

    vector<int> win(15,0), lose(15,0);
    for(int i=0;i<15;i++){
      for(int j=1;j<=7;j++){
	int nxt = (i+j)%15;
	if(use[i] && use[nxt]){
	  win[i] = 1; lose[nxt] = 1;
	}
      }
    }

    int id = -1;
    for(int i=0;i<15;i++){
      if(win[i] && !lose[i])id = i;
    }
    if(id<0)cout << "Draw" << endl;
    else cout << hands[id] << endl;
  }
}

Measured memory_bytes: 1212
gets=~/ /
K=K=$'.to_i,*(1..29).map{|i|K&(t=1<<i)>0?(K|t-1)^t:0}
x=[0]*30
$<.map{|s|a,b=s.split.map &:to_i;i=0;K.map{|k|(a|k)<=k&&x[i]+=b;i+=1}}
p x.max

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

#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb(s) push_back(s)
#define mp(a,b) make_pair(a,b)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define maxch(x,y) x=max(x,y)
#define minch(x,y) x=min(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt(x) bitset<32>(x).count()

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<P, int> PPI;
typedef pair<ll, ll> PL;
typedef pair<P, ll> PPL;

#define INF INT_MAX/3

#define MAX_N 1000

#define next nxt

int n;
int p[111111];
bool vis[111111];
int next[111111];
int d[111111];

int dfs(int v){
	if(p[v]==0)return v;
	if(next[v]!=-INF)return next[v];
	vis[v]=true;
	if(!vis[v+p[v]])return next[v]=dfs(v+p[v]);
	else return next[v]=-1;
}

int main(){
	cin.sync_with_stdio(false);
	cin>>n;
	rep(i,n)cin>>p[i];
	rep(i,n)next[i]=-INF;
	rep(i,n){
		memset(vis,0,sizeof(vis));
		next[i]=dfs(i);
	}
	fill(d,d+n,INF);
	priority_queue<P,vector<P>,greater<P> > que;
	que.push(P(0,0));
	d[0]=0;
	while(que.size()){
		P np=que.top(); que.pop();
		int v=np.se,dist=np.fi;
		if(v==n-1)break;
		repl(j,1,7){
			if(v+j>=n)continue;
			int nv=next[v+j];
			if(d[nv]>d[v]+1){
				d[nv]=d[v]+1;
				que.push(P(d[nv],nv));
			}
		}
	}
	cout<<d[n-1]<<endl;
	return 0;
}

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

int main(){
  int N,flag;
  cin >> N;
  flag=0; //変数flagが1である時,ひなあられの種類は4種類である。
  for(int i=0;i<N;i++){
    string color; //ひなあられの色
    cin >> color;
    if(color=="Y")flag=1;
  }
  if(flag==1)cout << "Four" << endl;
  else cout << "Three" << endl;
}

Measured memory_bytes: 3564
#include<bits/stdc++.h>
using namespace std;
int main(){
    int a;
    cin >> a;
    int count = 0;
    for(int i = 1;i<=a;i++){
        if(i < 10)
            count++;
        else if(100<=i&&i<1000)
            count++;
        else if(10000<=i && i<100000)
          count++;
    }
    cout << count << endl;
}


Measured memory_bytes: 384
#include <stdio.h>
#include <string.h>

int lcs(char x[], char y[])
{
  int i, j, m, n, a[1001][1001], max = 0;

  n = strlen(x);
  m = strlen(y);
  for (i = 0; i <= n; i++)
    a[i][0] = 0;
  for (j = 1; j <= m; j++)
    a[0][j] = 0;
  for (i = 1; i <= n; i++)
    for (j = 1; j <= m; j++){
      if (x[i-1] == y[j-1])
	a[i][j] = a[i-1][j-1]+1;
      else{
	if (a[i-1][j] >= a[i][j-1])
	  a[i][j] = a[i-1][j];
	else
	  a[i][j] = a[i][j-1];
      }
      if (a[i][j] > max)
	max = a[i][j];
    }
  
  return max;
}

int main()
{
  int i, q, c[150];
  char x[1000], y[1000];

  scanf("%d",&q);
  for (i = 0; i < q; i++){
    scanf("%s%s",x,y);
    c[i] = lcs(x,y);
  }
  for (i = 0; i < q; i++)
    printf("%d\n",c[i]);
  
  return 0;
}



Measured memory_bytes: 5656
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

int main() {
  string N;
  cin >> N;
  ll dp[1000002][2];
  dp[0][1] = 1;
  dp[0][0] = 0;

  for(int i = 0; i < (int)N.size(); i++) {
    int n = N[i]-'0';
    dp[i+1][0] = min(dp[i][0]+n, dp[i][1]+10-n);
    dp[i+1][1] = min(dp[i][0]+n+1, dp[i][1]+10-n-1);
  }
  
  cout << dp[N.size()][0] << endl;  
  return 0;
}

Measured memory_bytes: 20076
read N M
maru_data=$(cat)

cmd_str='grep -o -E "\-?[0-9]+\s\-?[0-9]+"'

c_d=$(echo $maru_data |eval $cmd_str |tail -n $M)
#echo $c_d
eval $(\
echo $maru_data | eval $cmd_str |head -n $N|
    awk ' {print("mae awk sqt {print(abs("$1"-one) + abs("$2"-two))} sqt ato")}' |
    sed "s/sqt/\'/g" | sed 's/one/$1/g' |sed 's/two/$2/g' | sed 's/abs\(([^\)]*)\)/sqrt((\1)^2)/g'|
    sed "s/mae/echo $(echo $c_d) |eval \$cmd_str | /g" |
    sed 's/ato/| cat -n | sort -n -s -k 2|head -n 1|cut  -f 1;/g' ) |tr -d " "




Measured memory_bytes: 3684
#include <iostream>

using namespace std;

int main()
{
    long long n,i,j=1;
    cin>>n;
    long long s[n+5];
    for(i=0;i<n;i++)
    {
        cin>>s[i];
        if(s[i]==0)
        j=0;
    }
    if(j==0)
        cout<<"0"<<endl;
    else
    {
        long long z=1;
        double x,y;
        for(i=0;i<n;i++)
        {
            y=(double)1000000000000000000;
            x=y/(double)z;
            if((double)s[i]>x)
            {
                cout<<"-1"<<endl;
                return 0;
            }
            else
                z=z*s[i];
                if(z>1000000000000000000)
                {
                    cout<<"-1"<<endl;
                    return 0;
                }
        }

        cout<<z<<endl;
    }
    /*if(101*9901*999999000001>1000000000000000000)
        cout<<"y"<<endl;
    else
        cout<<'n'<<endl;*/
    return 0;
}


Measured memory_bytes: 4404
#include <bits/stdc++.h>
using namespace std;
    int main(){
       int N;
     cin>>N;
     int a=N/100,b=(N/10)%10,c=N%10;
     if(a==7||b==7||c==7) cout<<"Yes"<<endl;
     else cout<<"No"<<endl;
 
    }

Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
int n,a[200010],x[200010],l,r;
inline bool check(int p)
{
	int i,l,r;
	for(i=1;i<=2*n-1;i++)
	  x[i]=(a[i]>=p);
	for(l=n;l>1 && x[l]!=x[l-1];l--);
	for(r=n;r<2*n-1 && x[r]!=x[r+1];r++);
	if(l==1 && r==2*n-1)
	  return x[n]^(n&1)^1;
	else if(n-l<r-n)
	  return x[l];
	else
	  return x[r];
}
int main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	int i;
	scanf("%d",&n);
	for(i=1;i<2*n;i++)
	  scanf("%d",&a[i]);
	for(l=1,r=2*n-1;l<r;)
	  if(check(l+r+1>>1))
	    l=(l+r+1>>1);
	  else
	    r=(l+r+1>>1)-1;
	printf("%d\n",l);
	return 0;
}


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

bool first_wins(const vector<int> &xs, const int k) {
    // winning on [i stones]
    vector<bool> dp(k + 1, false);

    for (int i = 1; i <= k; ++i) {
        for (const auto x : xs) {
            if (i - x >= 0 && !dp[i - x]) {
                dp[i] = true;
                break;
            }
        }
    }

    return dp[k];
}

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

    int n, k;
    cin >> n >> k;
    vector<int> xs(n, 0);
    for (auto &x : xs) cin >> x;

    cout << (first_wins(xs, k) ? "First" : "Second") << '\n';

    return 0;
}


Measured memory_bytes: 3684
import java.util.Scanner;

public class Main {

  static final long MOD = 998244353;

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int s = sc.nextInt();
    long dp[][] = new long[n + 1][s + 1];
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++) {
      int a = sc.nextInt();
      for (int j = 0; j <= s; j++) {
        dp[i][j] = (dp[i][j] + (2 * dp[i - 1][j])) % MOD;
        if (j >= a) {
          dp[i][j] = (dp[i][j] + dp[i - 1][j - a]) % MOD;
        }
      }
    }
    System.out.println(dp[n][s]);
  }
}


Measured memory_bytes: 111536
S=str(input())
T=str(input())
ls=len(S)
lt=len(T)
m=0
for i in range(ls-lt+1):
  A=S[i:i+lt]
  a=0
  for s,t in zip(A,T):
    if s==t:
      a+=1
  m=max(m,a)
print(lt-m)

Measured memory_bytes: 9124
#include <bits/stdc++.h>
using namespace std;
const long double PI = acos(-1);
typedef long long ll;
typedef pair<int64_t,int64_t> pll;
int dx[]={1,-1,0,0,1,-1,1,-1};
int dy[]={0,0,1,-1,1,-1,-1,1};
#define INF (2147483647)
#define mod (1000000007)
#define limit (7368791)
#define rep(i,a,b) for (int64_t i = (a); i < (b); i++)
#define REP(i,n) rep(i,0,n)
#define ALL(a) begin(a),end(a)
#define sz(s) (s).size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second

int gcd(int x,int y){
    if(y==0)return x;
    return gcd(y,x%y);
}

void solve(){
    int n,k;cin>>n>>k;
    int a[n];int mx=0;
    REP(i,n)cin>>a[i],mx=max(mx,a[i]);
    int g=INF;
    REP(i,n){if(mx==a[i])continue;g=min(g,gcd(mx,a[i]));}
    if(k>mx)cout<<"IMPOSSIBLE"<<endl;
    else if((mx-k)%g==0)cout<<"POSSIBLE"<<endl;
    else cout<<"IMPOSSIBLE"<<endl;
}
int main()
{
    cin.tie(0);
	ios::sync_with_stdio(false);
    solve();
    return 0;
}


Measured memory_bytes: 640
#include<iostream>
#include<algorithm>
#include<list>
#include<vector>
using namespace std;
typedef long long li;
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<(n);i++)
#define df 0
template<class T> void print(const T& t){ cout << t << "\n"; }
template<class T, class... Ts> void print(const T& t, const Ts&... ts) { cout << t; if (sizeof...(ts)) cout << " "; print(ts...); }


void dfs(vector<vector<int>>& adj,vector<int>& ans,const vector<li>& a,
         int parent=-1,int v=0){
  static vector<li> lis;
  
  auto itr=lower_bound(lis.begin(),lis.end(),a[v]);
  int flag=(itr!=lis.end());
  int k=itr-lis.begin();
  li memo;
  if(flag){
    memo=lis[k];
    lis[k]=a[v];
  } else lis.push_back(a[v]);
  
  ans[v]=lis.size();
  for(int x:adj[v]){
    if(x==parent) continue;
    dfs(adj,ans,a,v,x);
  }
  
  if(flag) lis[k]=memo;
  else lis.pop_back();
}

int main(){
  int n; cin >>n;
  vector<li> a(n);
  rep(i,n) cin >> a[i];
  vector<vector<int>> adj(n);
  rep(i,n-1){
    int u,v; cin >>u >>v; u--; v--;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  vector<int> ans(n,-1);
  dfs(adj,ans,a);
  
  rep(i,n) print(ans[i]);
}

Measured memory_bytes: 36700
from collections import defaultdict as dd
n,m = map(int, input().split())
dic = dd(list)
l = []
cnt = 0
for _ in range(m):
  a,b = map(int, input().split())
  l.append((a,b))
  dic[a].append(b)
  dic[b].append(a)
def con(x):
  visit.add(x)
  for i in dic[x]:
    if i in visit:
      continue
    con(i)
  return visit == set(range(1,n+1))
for x,y in l:
  dic[x].remove(y)
  dic[y].remove(x)
  visit = set()
  if not con(x):
    cnt += 1
  dic[x].append(y)
  dic[y].append(x)
print(cnt)

Measured memory_bytes: 3316
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
#define FOR(i,n,j) for(int i=(j);i<(n);++i)
#define rrep(i,n) for(int i=(n);i>=0;--i)
#define ssort(n) sort((n).begin(),(n).end())
using ll=long long;
using ld=long double;
typedef pair<int,int> P;
#define Yes cout << "Yes" << endl
#define No cout << "No" << endl
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
#define INF 10101010

int main()
{
    int n;
    cin >> n;
    vector<ll> a(n),b(n+1);
    vector<int> s(n);
    rep(i,n)cin >> a[i];
    ll money=1000;
    ll stock=0;
    rep(i,n-1){
        if(a[i]<a[i+1]){
            stock=money/a[i];
            money=money%a[i];
        }money+=a[i+1]*stock;
        stock=0;
    }
    cout << money << endl;

}

Measured memory_bytes: 3632
#include <stdio.h>

int main(void)
{
	int a,b,c;
	int keta;
	
	while (scanf("%d %d",&a,&b) != EOF) {
		c=a+b;
	
		keta=0;
		
		while(c!=0){
			c=c/10;
			++keta;
		}
		printf("%d\n",keta);	
	}
	

	return(0);
}

Measured memory_bytes: 600
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#include<complex>
#include<unordered_map>
#define deg(x) cout<<#x<<"="<<x<<endl;
#define fd(x) for(int i=0;i<x;i++)
#define fdd(a,x) for(int i=a;i<x;i++)
#define fx(x,n) for(int i=n-1;i>=x;i--)
#define mst(x) memset(x,0,sizeof(x));
#define fi first
#define se second
#define TB ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define ok "ok"
#define HH puts("");
#define ls rt<<1
#define rs rt<<1|1
#define pb(a,b) a.push_back(b);
#define FIN  freopen("1.in","r",stdin);
#define FOUT freopen("1.out","w",stdout);
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<string,int> pss;
typedef unsigned long long ull;
const ll mod=1e18;
const ll inf=1e18;
const double eps=1e-8;
const double pi=acos(-1);

char s[504050];
char q[303030];
char c[20];
int main(){
    TB
    cin>>s;
    int qq;
    cin>>qq;
    int flag=0,x,tot=0,fof=strlen(s);
    while(qq--){
        cin>>x;
        if(x==1){
            flag++;
        }else{
            int f;
            cin>>f>>c;
            if(f==1){
                if(flag&1){
                    s[fof++]=c[0];
                }else{
                    q[tot++]=c[0];
                }
            }else{
                if(flag&1){
                    q[tot++]=c[0];
                }else{
                    s[fof++]=c[0];
                }
            }
        }
    }
    if(flag&1){
        for(int i=fof-1;i>=0;i--) cout<<s[i];
        for(int i=0;i<tot;i++) cout<<q[i];
        cout<<'\n';
    }else{
        for(int i=tot-1;i>=0;i--) cout<<q[i];
        for(int i=0;i<fof;i++) cout<<s[i];
        cout<<'\n';
    }

    return 0;
}


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

using namespace std;

int Block[10000];


void change(int *pN) {
	int index;

	for (int i = 0; i < *pN; ++i) {
		--Block[i];
	}

	index = 0;
	for (int i = 0; i < *pN; ++i) {
		if (Block[i]) {
			Block[index++] = Block[i];
		}
	}
	Block[index++] = *pN;
	*pN = index;
}

int solve(int n) {
	int cnt;
	bool flag;

	cnt = 0;
	while (cnt <= 10000) {
		flag = true;
		for (int i = 0; i < n; ++i) {
			if (Block[i] != i + 1) {
				flag = false;
				break;
			}
		}
		if (flag) {
			return cnt;
		}
		++cnt;
		change(&n);
	}

	return -1;
}

int main() {
	int n;

	while (cin >> n, n) {
		memset(Block, 0, sizeof(Block));
		for (int i = 0; i < n; ++i) {
			cin >> Block[i];
		}
		cout << solve(n) << endl;
	}
	
	return 0;
}



Measured memory_bytes: 3136
#include<iostream>
using namespace std;

int main(){
  int a[10];
  int i;
  int j;
  for(i=0;i<10;i++){
    cin >> a[i];
      }for(i=0;i<10;i++){
    for(j=9;j>i;j--){
      if(a[j-1]<a[j]){
	int a1=a[j-1];
	  a[j-1]=a[j];
	  a[j]=a1;
      }}}
  for(i=0;i<3;i++)
    cout << a[i] << endl;
    return 0;
  }



Measured memory_bytes: 3104
#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main(int argc, char const *argv[])
{
    int H, W;
    cin >> H >> W;
    vector<string> a;
    string str;
    for (int i = 0; i < H; i++)
    {
        cin >> str;
        a.emplace_back(str);
    }

    for (int i = 0; i < W + 2; i++)
    {
        cout << '#';
    }
    cout << endl;

    for (string s : a)
    {
        cout << '#' << s << '#' << endl;
    }
    
    for (int i = 0; i < W + 2; i++)
    {
        cout << '#';
    }
    cout << endl;
    
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <complex>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iomanip>
#include <assert.h>
#include <array>
#include <cstdio>
#include <cstring>
#include <random>
#include <functional>
#include <numeric>
#include <bitset>
#include <fstream>

using namespace std;

struct before_main{before_main(){cin.tie(0); ios::sync_with_stdio(false);}} before_main;

#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
#define all(c) (c).begin(), (c).end()
#define zero(a) memset(a, 0, sizeof a)
#define minus(a) memset(a, -1, sizeof a)
template<class T1, class T2> inline bool minimize(T1 &a, T2 b) { return b < a && (a = b, 1); }
template<class T1, class T2> inline bool maximize(T1 &a, T2 b) { return a < b && (a = b, 1); }

typedef long long ll;
int const inf = 1<<29;

int N;
map<string, int> id;
bool adjacent[41][41];
int weight[41], wes[41];
int ans;

void dfs(ll S, int wsum, int curr) {
  if(wsum + wes[N-1] - (curr ? wes[curr-1] : 0) <= ans) return;
  if(curr == N-1) {
    ans = max(ans, wsum);
    return;
  }
  const int next = curr + 1;
  dfs(S, wsum, next);
  rep(k, next) if(adjacent[next][k] && (S >> k & 1)) return;
  dfs(S|(1LL<<next), wsum + weight[next], next);
}

int main() {

  while(cin >> N && N) {
    rep(i, 41) weight[i] = 0;
    rep(i, 41) rep(j, 41) adjacent[i][j] = 0;
    id.clear();
    int v = 0;

    rep(i, N) {
      string s; cin >> s;
      if(id.find(s) == id.end()) id[s] = v++;
      cin >> weight[id[s]];
      int n; cin >> n;
      rep(_, n) {
        string t; cin >> t;
        if(id.find(t) == id.end()) id[t] = v++;
        adjacent[id[s]][id[t]] = 1;
      }
    }

    rep(i, N) wes[i] = weight[i] + (i ? wes[i-1] : 0);

    ans = 0;
    dfs(1LL<<0, weight[0], 0);

    cout << ans << endl;

  }
  
  return 0;
}

Measured memory_bytes: 3176
#include <bits/stdc++.h>
#include <iostream>
//#include <algorithm>
// #include <iomanip>
#define ll long long

using namespace std;

const int MOD = 1000000007;

// 4 2
// 1 3
// 2 4

int main() {
  int n, m;
  scanf("%d %d", &n, &m);

  int left = 1;
  int right = n;
  for (int i = 0; i < m; i++) {
    int l, r;
    scanf("%d %d", &l, &r);

    left = max(left, l);
    right = min(right, r);
  }

  cout << max(0, (right - left + 1)) << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
constexpr ll mod = 1e9 + 7;
#define endl '\n'
 
bool IsGood(vector<ll>& A, ll K, ll len) {
  for (int i = 0; i < A.size(); ++i) {
    ll n_cut = (A[i]-1)/len;
    K -= n_cut;
    if (K < 0) return false;
  }
  return true;
}

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
 
  ll N,K;
  cin >> N >> K;
  vector<ll> A(N);
  for (auto& _a : A) cin >> _a;

  ll l = 0, r = 1e9+1;
  while (r-l > 1) {
    ll m = l + (r-l)/2;
    if (IsGood(A, K, m)) {
      r = m;
    } else {
      l = m;
    }
  }
  cout << r << endl;

}


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

int main() {
  int N, M, X;
  cin >> N >> M >> X;
  vector<int> C(N);
  vector<vector<int>> A(N, vector<int>(M));
  for (int i = 0; i < N; i++) {
    cin >> C.at(i);
    for (int j = 0; j < M; j++) {
      cin >> A.at(i).at(j);
    }
  }
  int ans = 1234567890;
   int all = 1<<N;
    for(int mask = 0; mask < all; mask++){
        vector<int> level(M);
        int cost = 0;
        for(int i = 0; i < N; i++){
            if((mask>>i)&1){
                cost += C.at(i);
                for(int j = 0; j < M; j++){
                    level.at(j) += A.at(i).at(j);
                }
            }
        }
      bool ok = true;
        for(int j = 0; j < M; j++){
            if(level.at(j) < X) ok = false;
        }
        if(ok) ans = min(ans,cost);
    }
    if(ans == 1234567890) cout << -1 << endl;
    else cout << ans << endl;
}
  

Measured memory_bytes: 3616
#![allow(unused_imports)]
#![allow(non_snake_case, unused)]

use std::cmp::*;
use std::collections::*;
use std::ops::*;

// https://atcoder.jp/contests/hokudai-hitachi2019-1/submissions/10518254

macro_rules! eprint {
	($($t:tt)*) => {{
		use ::std::io::Write;
		let _ = write!(::std::io::stderr(), $($t)*);
	}};
}
macro_rules! eprintln {
	() => { eprintln!(""); };
	($($t:tt)*) => {{
		use ::std::io::Write;
		let _ = writeln!(::std::io::stderr(), $($t)*);
	}};
}
macro_rules! dbg {
	($v:expr) => {{
		let val = $v;
		eprintln!("[{}:{}] {} = {:?}", file!(), line!(), stringify!($v), val);
		val
	}}
}

macro_rules! mat {
	($($e:expr),*) => { Vec::from(vec![$($e),*]) };
	($($e:expr,)*) => { Vec::from(vec![$($e),*]) };
	($e:expr; $d:expr) => { Vec::from(vec![$e; $d]) };
	($e:expr; $d:expr $(; $ds:expr)+) => { Vec::from(vec![mat![$e $(; $ds)*]; $d]) };
}

macro_rules! ok {
	($a:ident$([$i:expr])*.$f:ident()$(@$t:ident)*) => {
		$a$([$i])*.$f($($t),*)
	};
	($a:ident$([$i:expr])*.$f:ident($e:expr$(,$es:expr)*)$(@$t:ident)*) => { {
		let t = $e;
		ok!($a$([$i])*.$f($($es),*)$(@$t)*@t)
	} };
}

pub fn readln() -> String {
	let mut line = String::new();
	::std::io::stdin().read_line(&mut line).unwrap_or_else(|e| panic!("{}", e));
	line
}

macro_rules! read {
	($($t:tt),*; $n:expr) => {{
		let stdin = ::std::io::stdin();
		let ret = ::std::io::BufRead::lines(stdin.lock()).take($n).map(|line| {
			let line = line.unwrap();
			let mut it = line.split_whitespace();
			_read!(it; $($t),*)
		}).collect::<Vec<_>>();
		ret
	}};
	($($t:tt),*) => {{
		let line = readln();
		let mut it = line.split_whitespace();
		_read!(it; $($t),*)
	}};
}

macro_rules! _read {
	($it:ident; [char]) => {
		_read!($it; String).chars().collect::<Vec<_>>()
	};
	($it:ident; [u8]) => {
		Vec::from(_read!($it; String).into_bytes())
	};
	($it:ident; usize1) => {
		$it.next().unwrap_or_else(|| panic!("input mismatch")).parse::<usize>().unwrap_or_else(|e| panic!("{}", e)) - 1
	};
	($it:ident; [usize1]) => {
		$it.map(|s| s.parse::<usize>().unwrap_or_else(|e| panic!("{}", e)) - 1).collect::<Vec<_>>()
	};
	($it:ident; [$t:ty]) => {
		$it.map(|s| s.parse::<$t>().unwrap_or_else(|e| panic!("{}", e))).collect::<Vec<_>>()
	};
	($it:ident; $t:ty) => {
		$it.next().unwrap_or_else(|| panic!("input mismatch")).parse::<$t>().unwrap_or_else(|e| panic!("{}", e))
	};
	($it:ident; $($t:tt),+) => {
		($(_read!($it; $t)),*)
	};
}


pub fn main() {
	let _ = ::std::thread::Builder::new().name("run".to_string()).stack_size(32 * 1024 * 1024).spawn(run).unwrap().join();
}

const MOD: u32 = 1_000_000_007;
const INF: i64 = std::i64::MAX/3;

fn solve() {
	let (x,n) = read!(i64,usize);
	let a = read!([i64]);
	let mut ans = 0;
	let mut diff = INF;
	for i in 0..110 {
		let mut flag = true;
		for j in 0..n {
			if a[j]==i {
				flag = false;
			}
		}
		if !flag {
			continue;
		}
		if (x-i).abs()<diff {
			diff = (x-i).abs();
			ans=i;
		}
	}
	println!("{}",ans);
}

fn run() {
    solve();
}


Measured memory_bytes: 2216
#include<bits/stdc++.h>
#define Abra_Ka_Dabra ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using namespace std;

const long long mod = 1e9 + 7;
const double PI = acos(-1);
const double EPS = 1e-9;

ll bigMod(ll a, ll b, ll m) {
	if (b == 0) return 1 % m;
	if (b % 2 == 1) return (a * bigMod(a, b - 1, m)) % m;
	else {
		ll h = bigMod(a, b / 2, m);
		return (h * h) % m;
	}
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif

	Abra_Ka_Dabra

	ll x;
	cin >> x;
	ll x1 = bigMod(10, x, mod), x2 = (2 * bigMod(9, x, mod)) % mod , x3 = bigMod(8, x, mod);
	ll res = (x1 - x2 + x3) % mod;
	if (res < 0) res += mod;
	cout << res << "\n";


	return 0;
}


Measured memory_bytes: 3644
#include <bits/stdc++.h>
#include <fstream>
#include <stdlib.h>
#include <ctime>
typedef long long ll;

using namespace std;

int b[500000];
int a[500000];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << setprecision(100);
 //   freopen("input.txt","r",stdin);
    int n;
    cin >> n;
    for(int i = 0;i < n;i++) {
        cin >> b[i];
    }
  //  return 0;
    for(int i = n;i >= 1;i--) {
        int x=0;
        for(int j = 1;j*i <= n;j++){

            x+=a[j*i-1];
        }
        a[i-1]=(x+b[i-1])%2;
    }
    //return 0;
    int sz=0;
    int ans[500000];
    for(int i=0;i<n;i++){
      //  cout<<a[i]<<" ";
        if(a[i]%2 == 1){
            ans[sz]=i;
            sz++;
        }
    }
    cout<<sz<<'\n';
    for(int i=0;i<sz;i++) cout<<ans[i]+1<<" ";
    return 0;
}


Measured memory_bytes: 3072
#include <ctime>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <map>
using namespace std;
 
typedef long long ll;
typedef double lf;
typedef long double Lf;
typedef pair <int,int> pii;
typedef pair <ll, ll> pll;
 
#define TRACE(x) cerr << #x << "  " << x << endl
#define FOR(i, a, b) for (int i = (a); i < int(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define _ << " " <<
 
#define fi first
#define sec second
#define mp make_pair
 
ll n;
 
int main() {
	scanf("%lld",&n);
	int sol = (1 << 30);
	for (ll i = 0; i < min(1000000LL, n + 5); i++) {
		ll pre = i * (i + 1) / 2;
		if (pre >= n) {
			sol = i;
			break;
		}
	}
 
	printf("%d\n",sol);
	return 0;
}

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

int main() {
	int i, j, n, sum, cnt;
	while (1) {
		cin >> n;
		if (n == 0)break;
		cnt = 0;
		for (i = 1; i < n; i++){
			j = i;
			sum = 0;
			while (sum < n) {
				sum += j;
				j++;
			}
			if (sum == n)cnt++;
		}
		cout << cnt << endl;
	}




	return 0;
}

Measured memory_bytes: 3068