akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
#include<string.h>
int n,i,a[20],j,s,ans;
int main(){
    scanf("%d",&n);
    ans=1;
    for(i=0;i<n;i++){
        scanf("%d",&a[i]);
        ans*=3;
    }
    s=1;
    for(i=0;i<n;i++) if(a[i]%2==0) s*=2;
    ans-=s;
    printf("%d\n",ans);
}


Measured memory_bytes: 128
#include <cstdio>
#include <cctype>
#include <utility>
#include <algorithm>
#include <vector>
#include <complex>
using namespace std;

#define _gp(l) const auto gcu{getchar##l}; const auto pcu{putchar##l}
#ifdef __linux
_gp(_unlocked);
#else
_gp();
#endif
#define _DEF(r, n, ...) inline r n(__VA_ARGS__) noexcept
#define _T template <typename T>
#define _HT template <typename H,typename... T>
_T _DEF(T,in,int c){T n=0;int m=1;while(isspace(c)){c=gcu();}if(c=='-')m=-1,c=gcu();
	do{n=10*n+(c-'0'),c=gcu();}while(c>='0'&&c<='9');return m*n;}
_T _DEF(T,in,){return in<T>(gcu());}
_DEF(int,in,){return in<int>(gcu());}
struct _IN{inline operator int(){return in();}}IN;
#define _SCAN(...) _DEF(bool,scan,__VA_ARGS__)
_T _SCAN(T &n){int c=gcu();return c==EOF?n=0,false:(n=in<T>(c),true);}
_SCAN(char &c){c=gcu();gcu();return c!=EOF;}
#ifdef _GLIBCXX_STRING
_SCAN(string &s){int c;s="";
	for(;;){c=gcu();if(c=='\n'||c==' ')return true;else if(c==EOF)return false;s+=(char)c;}}
#endif
_HT _SCAN(H &h,T&&... t){return scan(h)&&scan(t...);}
#define _OUT(...) _DEF(void,out,__VA_ARGS__)
#define _OUTL(...) _DEF(void,outl,__VA_ARGS__)
_OUT(bool b){pcu('0'+b);} _OUT(const char *s){while(*s)pcu(*s++);} _OUT(char c){pcu(c);}
#ifdef _GLIBCXX_STRING
_OUT(string s){for(char c:s)pcu(c);}
#endif
_T _OUT(T n){static char b[20];char *p=b;T m=n<0?pcu('-'),-1:1;
	if(!n)*p++='0';else while(n)*p++=(char)(n%10*m+'0'),n/=10;while(p!=b)pcu(*--p);}
_OUTL(){out('\n');}
#ifdef _GLIBCXX_VECTOR
_T _OUT(vector<T> v){for(T &x:v)out(&x == &v[0]?"":" "),out(x);}
#endif
_HT _OUT(H&& h, T&&... t){out(h);out(move(t)...);}
template <typename... T> _OUTL(T&&... t){out(move(t)...);outl();}
struct range{
	int e,b=0,s=1; range(int _b,int _e,int _s):e(_e),b(_b),s(_s){} range(int _b,int _e): e(_e), b(_b){} range(int _e):e(_e){}
	struct it { int v, s; it (int _v, int _s) : v(_v), s(_s) {} operator int()const{return v;} operator int&(){return v;} int operator*()const{return v;}
		it& operator++(){v+=s;return *this;} }; it begin() {return {b, s};} it end() {return {e, s};}};

using P = complex<double>;

int main() {
	for (int n; (n = IN);) {
		vector<P> v(n), t;
		for (P &i: v) {
			double x, y;
			scanf("%lf,%lf", &x, &y);
			i = {x, y};
		}
		sort(begin(v), end(v), [](P a, P b) {return real(a) == real(b) ? imag(a) < imag(b) : real(a) < real(b);});
		auto f {[&](auto i, auto e, size_t s) {
			for (;i != e; i++) {
				while (t.size() > s && imag((t.back() - *(end(t) - 2)) * conj(*i - t.back())) <= 0)
					t.pop_back();
				t.push_back(*i);
			}
		}};
		f(begin(v), end(v), 1);
		f(rbegin(v) + 2, rend(v), t.size());
		outl(n - t.size() + 1);
	}
}


Measured memory_bytes: 2640
#include <cstdio>

int N, M, A, B;

int main() {
	scanf("%d%d%d%d", &N, &M, &A, &B);
	for (int i = 1; i <= N; ++i, puts(""))
		for (int j = 1; j <= M; ++j)
			printf("%d", (i <= B) ^ (j <= A));
	return 0;
}

Measured memory_bytes: 1152
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>
#define vv(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define vvi vector<vector<int> >
#define vvl vector<vector<ll> >
#define vll vector<ll>
#define rep(c, a, b) for(ll c=a;c<b;c++)
#define re(c, b) for(ll c=0;c<b;c++)
typedef long long int ll;
typedef long double ld;
using namespace std;

struct Dijkstra{
  ll INF=1000000000000000009;
  ll MAX_V=1000000;
  ll st = -1;
  struct edge{ll to, cost;};
  typedef pair<ll, ll> p;
  vector<vector<edge>> G;
  vector<ll> pre, d, d2;
  priority_queue<p, vector<p>, greater<p> > que; //class, inner, compair
  Dijkstra(ll s){
    G.resize(s+2);
    pre.resize(s+2, -1);
    d.resize(s+2, INF);
    d2.resize(s+2, INF);
  }
  inline void insert(ll a, ll b, ll c){
    G[a].push_back(edge{b, c});
  }
  void init(){
    for(int i=0;i<d.size();i++) pre[i] = -1, d[i] = d2[i] = INF;
  }
  void dijkstra(int start){
    init();
    st = start;
    d[start]=0;
    que.push(p(0, start));
    while(!que.empty()){
      p p_now=que.top(); que.pop();
      ll v = p_now.second;
      if(d[v]<p_now.first) continue;
      for(int i=0;i<G[v].size();i++){
        edge e = G[v][i];
        if(d[e.to]>d[v]+e.cost){
          d[e.to]=d[v]+e.cost;
          pre[e.to] = v;
          que.push(p(d[e.to], e.to));
        }
      }
    }
  }
  void dijkstra2(int start){
    st = start;
    d2[start]=0;
    que.push(p(0, start));
    while(!que.empty()){
      p p_now=que.top(); que.pop();
      ll v = p_now.second;
      if(d2[v]<p_now.first) continue;
      for(int i=0;i<G[v].size();i++){
        edge e = G[v][i];
        if(d2[e.to]>d2[v]+e.cost){
          d2[e.to]=d2[v]+e.cost;
          pre[e.to] = v;
          que.push(p(d2[e.to], e.to));
        }
      }
    }
  }
  vll get_path(int now){
    vll ret;
    while(now!=-1){
      ret.push_back(now);
      now = pre[now];
    }
    return ret;
  }
};
int main(int argc, char const *argv[]) {
  ll a, b, c, d, n, m, s, t;std::cin >> n >> m >> s >> t;
  Dijkstra dk(2*n+1);
  re(i, m){
    std::cin >> a >> b >> c >> d;
    dk.insert(a, b, c);
    dk.insert(b, a, c);
    dk.insert(a+n, b+n, d);
    dk.insert(b+n, a+n, d);
  }
  vll ans(n+1, 0);
  dk.dijkstra(s);
  dk.dijkstra2(t+n);
  ll x = 1000000000000000;

  for(int i=n;i>0;i--){
    if(dk.d[i]==dk.INF||dk.d2[i+n]==dk.INF){
      ans[i] = ans[i+1];
      continue;
    }
    ll now = x - (dk.d[i] + dk.d2[i+n]);
    ans[i] = max((i==n?0:ans[i+1]), now);
  }
  rep(i, 1, n+1) std::cout << ans[i] << '\n';
  return 0;
}


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

// int/long:		-2,147,483,648 - 2,147,483,647 (-2^31 <= int < 2^31)
// long/long long:	-9,223,372,036,854,775,808 - 9,223,372,036,854,775,807 (-2^63 <= long < 2^63)

#define	INF (1<<30)
//1,073,741,824
//= 536,870,912 *2

#define	MOD 1000000007

#define	Rep0(i, n)	for (int i=0; i<n; i++)
#define	Rep1(i, n)	for (int i=1; i<=n; i++)
#define Sort(P)	sort(P.begin(), P.end())
#define Rev(P)	reverse(P.begin(), P.end())

int	main() {
	ll N, K;
	cin >>N >>K;
	ll S=0;
	ll INV2 = MOD-(MOD/2)%MOD;
	for (ll i=K; i<=N+1; i++) {
		ll S0=(i-1)*i;
		S0 %=MOD;
		S0 *=INV2;
		S0 %=MOD;
		ll S1=(N*2-i+1)*i;
		S1 %=MOD;
		S1 *=INV2;
		S1 %=MOD;
		S +=S1-S0+1;
		S +=MOD;
		S %=MOD;
	}
	cout <<S <<endl;
	return 0;
}



Measured memory_bytes: 3624
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back

using namespace std;
const long long MOD = (long long)1e9 + 7;

int r, d, x;

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> r >> d >> x;
    for (int i = 0; i < 10; i++) {
        int cur;
        cur = r*x - d;
        cout << cur << "\n";
        x = cur;
    }
    //system("pause");
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

typedef long long ll;
const int N = 2e5 + 10, OO = 0x3f3f3f3f, mod = 1e9 + 7;

#define PI acos(-1)
#define clr(arr, val) memset(arr, val, sizeof(arr))
#define loop(i, n) for (int i = 0; i < int(n); i++)
#define rloop(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define xloop(i, a, b) for (int i = int(a); i <= int(b); i++)
#define ALL(v) ((v).begin()), ((v).end())
#define SZ(v) ((int)((v).size()))
//int dx[] = {1, 0, -1, 0};
//int dy[] = {0, 1, 0, -1}; //4 Direction
//int dx[] = {1, 1, 0, -1, -1, -1, 0, 1};
//int dy[] = {0, 1, 1, 1, 0, -1, -1, -1}; //8 direction
int dx[]={2,1,-1,-2,-2,-1,1,2};int dy[]={1,2,2,1,-1,-2,-2,-1};//Knight Direction
//int dx[6]={2,1,-1,-2,-1,1};int dy[6]={0,1,1,0,-1,-1}; //Hexagonal Direction

//-- "كلٌّ من يسعى لابد يصل .. كلٌّ من يسعى مضمون له الوصول" --//

int n ,a[N];

int main()
{
    //ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	
	
	scanf("%d", &n);
	for(int i = 0 ; i < n ; ++i)
		scanf("%d",  a+ i);
	
	if(n == 1)
		puts("0");
	else{
		ll sum = 0;
		for(int i = 1 ; i < n ; ++i){
			if(a[i] - a[i-1] < 0){
				int dif = a[i-1] - a[i];
				a[i] += dif;
				sum += dif;
				//printf("%lld\n" , sum);
			}
		}
		printf("%lld\n", sum);
	}
	
	
	
    return 0;
}




Measured memory_bytes: 4600
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rrep(i,a,b) for(int i=(int)(a);i>=(int)(b);--i)
#define fore(i,a) for(auto &i:a)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define isin(i,a,b) ((a) <= (i) && (i) < (b))
#define uni(a) (a).erase(unique(all(a)),(a).end())
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)(a).size()
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
using ll  = long long;
using unit= unsigned;
using ull = unsigned long long;
using P   = pair<int,int>;
using vi  = vector<int>;
using vl  = vector<ll>;
using vvi = vector<vi>;
using vp  = vector<P>;
void _main(); int main(){ cin.tie(0); ios::sync_with_stdio(false); _main(); }
template<class T>void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
template<class T>void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T>void POSS(T condition){ if(condition) cout << "POSSIBLE" << endl; else cout << "IMPOSSIBLE" << endl; }
template<class T>void Poss(T condition){ if(condition) cout << "Possible" << endl; else cout << "Impossible" << endl; }
template<class T>bool chmax(T &a, const T &b){ if (a<b){ a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b){ if (b<a){ a = b; return 1; } return 0; }
template<class T>T gcd(T a, T b){ if (b==0){ return a; }else{ return gcd(b, a%b); }}
template<class T>T lcm(T a, T b){ return a / gcd(a, b) * b; }
constexpr double eps = 1e-10;
constexpr int inf = INT_MAX / 2;
constexpr ll infl = 1LL << 60;

void _main() {
  int N, M;
  cin >> N >> M;
  vi L(M), R(M);
  rep(i, 0, M) cin >> L[i] >> R[i];
  
  int l = *max_element(all(L));
  int r = *min_element(all(R));
  int ans = max(0, r - l + 1);
  cout << ans << endl;
}

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

int main(){
    int n;
    cin >> n;
    int t = n/100;
    int tmp = t+t*10+t*100;
    if (tmp >= n) cout << tmp << endl;
    else cout << tmp+111 << endl;
    return 0;
}


Measured memory_bytes: 256
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <algorithm>
#include <climits>
#include <cmath>
#include <cstring>
#include <forward_list>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;
typedef long long ll;
typedef pair<int, int> P;

const ll MOD = 1E+09 + 7;
const ll INF = 1E18;
const int MAX_N = 1E+05;

ll N;
ll A, B;

ll H[MAX_N];

bool canEliminate(ll n);

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> A >> B;

    ll hmax = 0;
    for (int i = 0; i < N; i++) {
        cin >> H[i];
        hmax = max(hmax, H[i]);
    }

    ll nmin = 0;
    ll nmax = ceil(double(hmax) / B);
    while (true) {
        ll nmid = (nmin + nmax) / 2;
        if (nmid == nmax || nmid == nmin) {
            break;
        }
        if (canEliminate(nmid)) {
            nmax = nmid;
        } else {
            nmin = nmid;
        }
    }

    cout << nmax << "\n";

    return 0;
}

bool canEliminate(ll n)
{
    ll cnt = 0;
    for (int i = 0; i < N; i++) {
        if (H[i] >= n * B) {
            ll h = H[i] - n * B;
            cnt += ceil(double(h) / (A - B));
        }
    }
    return cnt <= n;
}

Measured memory_bytes: 4404
while True:
	n=input().split()
	n[0]=int(n[0])
	n[1]=int(n[1])
	if n[0]==0 and n[1]==0:
		break

	if n[0]>n[1]:
		c=n[0]
		n[0]=n[1]
		n[1]=c
	print(n[0],n[1])


Measured memory_bytes: 5616
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int main(){
  string s; cin >> s;

  for(int i=0; i<s.length()-2; i++){
    if(s[i] == s[i+2]){
      cout << i+1 << " " << i+3 << endl;
      return 0;
    }
  }

  for(int i=0; i<s.length()-1; i++){
    if(s[i] == s[i+1]){
      cout << i+1 << " " << i+2 << endl;
      return 0;
    }
  }
  
  cout << -1 << " " << -1 << endl;

  return 0;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1e9;
const int MOD = INF+7;
const ll LINF = 1e18;
#define rep(i,N) for(int (i)=0;(i)<(N);++(i))
#define rrep(i,N) for(int (i)=(N-1);(i)>0;--i)
#define FOR(i,j,N) for(int (i)=(j);(i)<(N);++(i))
#define put(n) cout<<(n)<<endl;
#define all(v) v.begin(),v.end()
#define MP make_pair
#define pb(n) push_back(n)
#define int long long 

vector<int> N[5];

signed main(){
   
    rep(i,3){
        int a,b;
        cin >> a >> b;
        N[a].push_back(b);
        N[b].push_back(a);
    }
    for(auto i : N){
        if(i.size() == 3) {
            cout << "NO" << endl;
            return 0;
        }
    }

    cout << "YES" << endl;
}

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

int N, store[110], mat[110][15];
const int INF = 1 << 30;

int main() {
    scanf("%d", &N);
    for(int i=0; i<N; i++) {
        int bit = 0;
        for(int k=0; k<10; k++) {
            int val; scanf("%d", &val);
            bit = (bit << 1) | val;
        }
        store[i] = bit;
    }

    for(int i=0; i<N; i++) {
        for(int j=0; j<=10; j++) {
            scanf("%d", &mat[i][j]);
        }
    }

    int ans = -INF;
    for(int bit=1; bit<(1<<10); bit++) {
        int tmp = 0;
        for(int i=0; i<N; i++) {
            int cnt = __builtin_popcount(bit & store[i]);
            tmp += mat[i][cnt];
        }
        ans = std::max(ans, tmp);
    }
    printf("%d\n", ans);
    return 0;
}

Measured memory_bytes: 128
#include <cstdio>

using namespace std;

int main() {
    int n, a, b;
    int sums = 0;
    scanf("%d %d %d", &n, &a, &b);
    for (int i = 1; i <= n; i++) {
       int some = i;
       int sum = 0;
       while (some > 0) {
           sum += some % 10;
           some /= 10;
       }
       if (sum >= a && sum <= b) {
           sums += i;
       }
    }
    printf("%d\n", sums);
    return 0;
}


Measured memory_bytes: 636
#include <bits/stdc++.h>
typedef long long LL;
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)

using namespace std;

int main(void)
{
  string s;
  cin >> s;
  int l=0;
  int answer=s.size();
  if(s.front()==s.back()) ++answer;
  cout << (answer%2?"First":"Second") << endl;
}


Measured memory_bytes: 512
b = {}
b['gray'] = 0
b['brown'] = 0
b['green'] = 0
b['cyan'] = 0
b['blue'] = 0
b['yellow'] = 0
b['orange'] = 0
b['red'] = 0
b['other'] = 0

n = int(input())
a = list(map(int,input().split()))

for ai in a:
    if ai < 400:
        b['gray'] += 1
    elif ai < 800:
        b['brown'] += 1
    elif ai < 1200:
        b['green'] += 1
    elif ai < 1600:
        b['cyan'] += 1
    elif ai < 2000:
        b['blue'] += 1
    elif ai < 2400:
        b['yellow'] += 1
    elif ai < 2800:
        b['orange'] += 1
    elif ai < 3200:
        b['red'] += 1
    else:
        b['other'] += 1

ans = 0
for k, v in b.items():
    if k != 'other' and v > 0:
        ans += 1

if ans == 0:
    print(1, b['other'])
else:
    print(ans, ans + b['other'])


Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <math.h>
#include <cassert>
#define rep(i,n) for(int i = 0; i < n; ++i )
using namespace std;
using ll = long long;
using P = pair<int,int>;

const int INF = 1000;
int main() {
  vector<int> x(5);
  rep(i,5) cin >> x[i];
  
  int ans = 0;
  rep(i,5) ans += (x[i]+9)/10*10;
  int m = INF;
  rep(i,5) if(x[i]%10!=0) m = min(m,x[i]%10);
  if(m != INF) ans -= 10-m;
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <string>
#include <iostream>
#include <vector>
#include <stack>
#include <stdio.h>
#include <math.h>
#include <utility>
#include <algorithm>


class UnionFind {
public:
	std::vector<int> parent;
	UnionFind(int n) {
		parent = std::vector<int>(n, -1);
	}
	int root(int i) {
		//自分が親なら
		if (parent[i] < 0) {
			return i;
		}
		else {
			//接続を親の真下に更新
			return parent[i] = root(parent[i]);
		}
	}
	int size(int i) {
		return -parent[root(i)];
	}
	bool connect(int i, int j) {
		int pi = root(i);
		int pj = root(j);
		if (pi == pj) return false;
		if (pi < pj) {
			std::swap(pi, pj);
		}
		parent[pi] += -size(pj);
		parent[pj] = pi;
		return true;
	}
};

int main()
{
	int n, m;
	std::cin >> n >> m;
	std::vector<int> a(m,-1), b(m,-1);
	for (int i = 0; i < m; i++) {
		std::cin >> a[i] >> b[i];
		a[i] --;
		b[i] --;
	}
	UnionFind uf(n);

	std::vector<long long> disa(m);
	//最後の不便さ combinationの式から
	disa[m - 1] = (long long)n*(n-1)/2;
	for (int i = m - 1; i > 0; i--) {
		disa[i - 1] = disa[i];
		if (uf.root(a[i])!=uf.root(b[i])) {
			disa[i - 1] -= (long long)uf.size(a[i])*uf.size(b[i]);//new link group
			uf.connect(a[i], b[i]);
		}
	}

	for (int i = 0; i < m; i++) {
		std::cout << disa[i] << std::endl;
	}

	return 0;
}

Measured memory_bytes: 3328
n = int(input())
dish = [int(i) for i in input().split()]
satisfy = [int(i) for i in input().split()]
bonus = [int(i) for i in input().split()]

ans = 0
pre = -1
for d in dish:
  ans += satisfy[d-1]
  if d == pre + 1:
    ans += bonus[d-2]
  pre = d

print(ans)

Measured memory_bytes: 38384
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;
using ll = long long;
#define REP(i, n) for (int i = 0; i < n; ++i)
struct E {
	int to, cost;
};
using G = vector<vector<E>>;
vector<int> p;
G g;
constexpr ll inf = 1e18 + 1;
int n, w;

vector<ll> rec1(const vector<ll> &x, int v, int par) {
	auto a = x;
	for (auto e : g[v]) {
		if (e.to != par) {
			auto tmp = rec1(a, e.to, v);
			REP(i, w + 1 - e.cost) {
				a[i + e.cost] = max(a[i + e.cost], tmp[i]);
			}
		}
	}
	REP(i, w + 1) {
		a[i] += p[v];
	}
	return a;
}
vector<ll> rec0(int v, int par) {
	vector<ll> ret(w + 1, -inf);
	ret[0] = 0;
	vector<ll> z(w + 1, -inf);
	z[0] = 0;
	for (auto &&e : g[v]) {
		if (e.to != par) {
			auto tmp = rec0(e.to, v);
			REP(i, w + 1) {
				ret[i] = max(ret[i], tmp[i]);
			}
			auto tmp1 = rec1(z, e.to, v);
			REP(i, w + 1) {
				ret[i] = max(ret[i], tmp1[i]);
			}
		}
	}
	return ret;
}

int main() {

	cin >> n >> w;
	p.resize(n);
	REP(i, n) cin >> p[i];
	g.resize(n);
	REP(i, n - 1) {
		int a, b, c;
		cin >> a >> b >> c;
		a--;
		b--;
		g[a].push_back(E{b, c});
		g[b].push_back(E{a, c});
	}
	vector<ll> ans = rec0(0, -1);
	vector<ll> init(w + 1, -inf);
	init[0] = 0;
	vector<ll> ans1 = rec1(init, 0, -1);
	ll res = -inf;
	res = max(res, *max_element(begin(ans), end(ans)));
	res = max(res, *max_element(begin(ans1), end(ans1)));
	cout << res << endl;
	//cerr << "test" << endl;
}



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

using namespace std;
using ll=long long;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, a, n) for(int i = (a); i < (n); i++)

int main(){
  cin.tie(nullptr);ios_base::sync_with_stdio(false);
  int n,hoge=111;cin>>n;
  while(n>hoge){
    hoge+=111;
  }
  cout<<hoge<<endl;
}


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

int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  int sum=0;
  for(int i=0;i<n;i++){
    cin >> a.at(i);
    sum+=a.at(i);
  }
  cout << sum-n << endl;
}

Measured memory_bytes: 256
s=input()
T=input()
ans=[]
for i in range(len(s)-len(T)+1):
  flag=True
  S=s[:i]+T+s[i+len(T):]
  for j in range(len(T)):
    if(s[i+j]!="?" and s[i+j]!=T[j]):
      flag=False
  if(flag==True):
    S.replace("?","a")
    #print(S)
    ans.append(S.replace("?","a"))

if(ans):
  ans.sort()
  print(ans[0])
else:
  print("UNRESTORABLE")

Measured memory_bytes: 3064
#include<iostream>
using namespace std;
#define MAX 500000
#define SENTINEL 2000000000
int l[MAX/2+2],r[MAX/2+2];
int cur;
void merge(int A[],int n,int left,int mid,int right)
{
    int n1=mid-left;
    int n2=right-mid;
    for(int i=0;i<n1;i++)
    {
        l[i]=A[left+i];
    }
    for(int i=0;i<n2;i++)
    {
        r[i]=A[mid+i];
    }
    l[n1]=r[n2]=SENTINEL;
    int i=0,j=0;
    for(int k=left;k<right;k++)
    {
        cur++;
        if(l[i]<=r[j])
        {
            A[k]=l[i++];
        }else{
        A[k]=r[j++];
        }
    }
}
void mergesort(int A[],int n,int left,int right)
{
    if(left+1<right){
        int mid=(left+right)/2;
        mergesort(A,n,left,mid);
        mergesort(A,n,mid,right);
        merge(A,n,left,mid,right);
    }
}
int main()
{
    int A[MAX],n,i;
    cur=0;
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>A[i];
    }
    mergesort(A,n,0,n);
    for(i=0;i<n;i++)
    {
        if(i)cout<<" ";
        cout<<A[i];
    }
    cout<<endl;
    cout<<cur<<endl;
    return 0;
}

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

using namespace std;

typedef uint64_t u64;
typedef int64_t s64;
typedef uint32_t u32;
typedef int32_t s32;
typedef vector<s32> vs32;
typedef vector<u32> vu32;
typedef vector<s64> vs64;
typedef vector<u64> vu64;

const double PI=3.14159265358979323846;

#define MAX(x, y) ((x) < (y) ? (y) : (x))
#define MIN(x, y) ((x) > (y) ? (y) : (x))

#define rep(i, N) for(int i = 0; i < N; ++i)

#define CEIL(x, y) (((x) + (y) - 1) / (y))
#define MOD 1000000007ULL

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

    int H, W;
    cin >> H >> W;

    vector<vs32> A(H, vs32(W));
    vector<vs32> B(H, vs32(W));
    rep (h, H) rep (w, W) cin >> A[h][w];
    rep (h, H) rep (w, W) cin >> B[h][w];

    vector< vector< vector <bool> > > dp(H, vector< vector<bool> >(W, vector<bool>((H + W) * 80 + 1, false)));
    dp[0][0][abs(A[0][0] - B[0][0])] = true;
    for (int h = 0; h < H; ++h)
    {
        for (int w = 0; w < W; ++w)
        {
            for (int k = 0; k <= (H + W) * 80; ++k)
            {
                if (dp[h][w][k])
                {
                    if (h < H - 1)
                    {
                        int d = abs(A[h + 1][w] - B[h + 1][w]);
                        dp[h + 1][w][abs(k - d)] = true;
                        dp[h + 1][w][abs(k + d)] = true;
                    }
                    if (w < W - 1)
                    {
                        int d = abs(A[h][w + 1] - B[h][w + 1]);
                        dp[h][w + 1][abs(k - d)] = true;
                        dp[h][w + 1][abs(k + d)] = true;
                    }
                }
            }
        }
    }

    int ans;
    for (ans = 0; ans <= (H + W) * 80 && !dp[H - 1][W - 1][ans]; ++ans);
    cout << ans << "\n";
    return 0;
}



Measured memory_bytes: 10752
#include <bits/stdc++.h>
using namespace std;
long long int mod=1e9 +7;
 
long long int fast_exp(long long int base,long long int ex) {
    long long int res=1;
    while(ex>0) {
       if(ex%2==1) res=(res*base)%mod;
       base=(base*base)%mod;
       ex/=2;
    }
    return res%mod;
}
long long int gcd(long long int a, long long int b)
{
    if(b==0)return a;
    else return gcd(b,a%b);
}
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
        string s;int k;
        cin>>s>>k;
        if(k==1)
        {
            cout<<s[0]<<"\n";return 0;
        }
int u=0;int y=0;
while(s[u++]=='1'){ if(u==k){cout<<"1\n";return 0;}
if(u==s.length())break;}
    for(int i=0;i<s.length();i++)
    {
        if(s[i]!='1'){cout<<s[i]<<"\n";return 0;}
    }
if(k>s.length())
{while(1){1;}}
  cout<<"1\n";return 0;
   return 0;
}

Measured memory_bytes: 256
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
using namespace std;

#define FOR(i,f,t) for(int i=(int)f; i<(int)t; i++)
#define FORR(i,f,t) for(int i=(int)f; i>(int)t; i--)
#define ms(obj, val) memset(obj, val, sizeof(obj))
#define pb push_back
#define SYNC ios_base::sync_with_stdio(false)
#define inf 2248012
#define mp make_pair
#define F first
#define S second
#define ri(x) scanf("%d",&x)
#define rii(x,y) scanf("%d %d",&x,&y)
#define riii(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define lri(x) scanf("%lld",&x)
#define lrii(x,y) scanf("%lld %lld",&x,&y)
#define lriii(x,y,z) scanf("%lld %lld %lld",&x,&y,&z)

typedef vector<int> vi;
typedef long long ll;
typedef pair<int, int> ii;

const int MAXN = 1e5+3; //AREGLAAAAAAAAR!!!!

int main(){
	SYNC;
	string s;
	string t;
	string d;
	cin>>s>>t;
	d=t;
	FOR(i,0,t.size()) d+=t[i];
	if(s.size()!=t.size()){
		printf("No\n");
		return 0;
	}
	FOR(i,0,d.size()){
		int u=0; int good=1;
		FOR(j,0,s.size()){
			if(i+u<d.size() && s[j]==d[i+u]){
				u++;
				continue;
			}
			good=0;
			break;
		}
		if(good){
			printf("Yes\n");
			return 0;
		}
	}	
	printf("No\n");
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
typedef long long ll;
using P = pair<int, int>;
const int INF = 1001001001;
ll MOD = 1e9 + 7;
int A = 0, G = 1, C = 2, T = 3;

// A=0,G=1,C=2,T=3

int main() {
  int n;
  cin >> n;

  ll dp[n + 1][4][4][4];
  rep(i, n + 1) rep(j, 4) rep(k, 4) rep(l, 4) dp[i][j][k][l] = 0;

  rep(j, 4) rep(k, 4) rep(l, 4) {
    if (j == 0 && k == 1 && l == 2) continue;
    if (j == 0 && k == 2 && l == 1) continue;
    if (j == 1 && k == 0 && l == 2) continue;
    dp[3][j][k][l] = 1;
  }

  for (int i = 4; i <= n; i++) {
    rep(j, 4) {
      rep(k, 4) {
        rep(l, 4) {
          rep(m, 4) {
            if (k == 0 && l == 1 && m == 2) continue;
            if (k == 0 && l == 2 && m == 1) continue;
            if (k == 1 && l == 0 && m == 2) continue;
            if (j == 0 && l == 1 && m == 2) continue;
            if (j == 0 && k == 1 && m == 2) continue;
            dp[i][k][l][m] += dp[i - 1][j][k][l] % MOD;
            dp[i][j][k][l] %= MOD;
          }
        }
      }
    }
  }

  ll ans = 0;
  rep(j, 4) {
    rep(k, 4) {
      rep(l, 4) {
        ans += dp[n][j][k][l] % MOD;
        ans %= MOD;
      }
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
int main(){
  int n,m,x;
  cin >> n >> m >> x;
  int a[n][m];
  int c[n];
  rep(i,n){
    cin >> c[i];
    rep(j,m){
      cin >> a[i][j];
    }
  }
  int ans=1e9;
  for(int bit=0;bit<(1<<n);bit++){
    int mini=0;
    vector<int> is(m);
    rep(i,n){
      if(bit&(1<<i)){
        mini+=c[i];
        for(int j=0;j<m;j++){
          is.at(j)+=a[i][j];
        }
      }
    }
    bool pq=true;
    for(int j=0;j<m;j++){
      if(is.at(j)<x){
        pq=false;
      }
    }
    if(pq){
      ans=min(ans,mini);
    }
  }
  if(ans==1e9){
    ans=-1;
  }
  cout <<ans;
}

Measured memory_bytes: 3612
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define l long
#define pb push_back
#define mp make_pair
#define mt make_tuple

int gcd(int a,int b)
{
    if(b>a) return gcd(b,a);
    if(b==0) return a;
    return gcd(b,a%b);
}

int main() {
	// your code goes here
	//ifstream cin("input.txt");
	//ofstream cout("output.txt");
	ios_base::sync_with_stdio(false); 
    cin.tie(NULL); 
	int k; cin>>k;
	int ans=0;
	for(int i=1;i<=k;i++)
	{
	    for(int j=1;j<=k;j++)
	    {
	        for(int p=1;p<=k;p++)
	        {
	            if( i==1||j==1||p==1 ){ ans++; continue; }
	            int tt = gcd(i,j);
	            if(tt==1){ ans++; continue; }
	            ans += gcd(tt,p);
	        }
	    }
	}
	cout<<ans;
	
	return 0;
}


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

#define M_PI       3.14159265358979323846

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(); }
inline int readInt() { int x; scanf("%d", &x); return x; }

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<int, PII> TIII;
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;


//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 SQ(a) ((a)*(a))
#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 SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,s,n) for(int i=s;i<(int)n;++i)
#define REP(i,n) FOR(i,0,n)
#define MOD 1000000007

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()

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

#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)


struct Edge {
    int to, from;
    ll cost;
    Edge(int from, int to, ll cost): from(from), to(to), cost(cost) {}
};

typedef vector<vector<Edge>> AdjList;
AdjList graph;

int a[200010];
int main() {
    //cin.tie(0);
    //ios::sync_with_stdio(false);
    //cout << fixed << setprecision(10);

    int N; cin >> N;
    REP(i, N) cin >> a[i];

    
    ll ans=0;
    int bit_balley[29]={0};
    // for(int i=0; i<N; ++i){
    //     for(int j=i; j<N; ++j){
    //         int lhs=0, rhs=0;
    //         for(int k=i; k<=j; ++k){
    //             lhs += a[k];
    //             rhs ^= a[k];    
    //         }
    //         if(lhs == rhs) {
    //             ans++;
    //         cout << i << " " << j << endl;
    //     }}
    // }

    int right=0;
    for(int left = 0; left < N; ++left){
        while(right < N){
            int t = a[right];
            int temp[29]={0};
            for(int i=0; i<29; ++i){
                if(t%2==1) temp[i] = 1;
                t /= 2;
            }

            bool c = true;
            for(int i=0; i<29; ++i){
                if(bit_balley[i] == 1 && temp[i]==1) {
                    c = false;
                }
            }
            if(!c) break;
            for(int i=0; i<29; ++i){
                bit_balley[i] += temp[i];
            }
            right++;
        }

        ll len = right-left;
        ans += len;

        if(right == left) right++;
        else{
            int t = a[left];
            for(int i=0; i<29; ++i){
                if(t%2==1) bit_balley[i]=0;
                t/=2;
            }
        }
    }
    cout << ans << endl;
    return 0;

}

Measured memory_bytes: 1024
#include <iostream>
#include <cmath>
#include <map>
#include <utility>
#include <list>
#include <string>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

#define LL long long


int main() {
    int a, b, k;
    cin >> a >> b >> k;

    int c[100];
    int n = 0;
    int i = 1;
    while (i <= 100) {
        if (a % i == 0 && b % i == 0) {
            c[n] = i;
            n++;
        }
        i++;
    }

    cout << c[n - k] << endl;
    
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main() {
    long long a,b;
    cin>>a>>b;
    if(a>b)
        swap(a, b);
    if(a==1&&b==1)
        printf("1\n");
    else if(a==1)
        printf("%lld\n",b-2);
    else if(a==2)
        printf("0\n");
    else{
        printf("%lld\n",(a-2)*(b-2));
    }
    return 0;
}

Measured memory_bytes: 256
package main

import "fmt"

func main() {
	var N int
	fmt.Scan(&N)
	for i := 1; i <= 9; i++ {
		for j := 1; j <= 9; j++ {
			if i*j == N {
				fmt.Println("Yes")
				return
			}
		}
	}
	fmt.Println("No")
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#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 rep2(i,j,n) for(int j=i;j<n;j++)
#define rep3(i,j,n) for(int j=i;j<=n;j++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define sp(n) cout << fixed << setprecision(n)
typedef long long ll;
using namespace std;
// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
const int mod = 1000000007;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const {
    return pow(mod-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res/=a;
  }
};

ll modpow(ll a, ll n){
  ll r = 1;
  while (n) {
    r = r * ( (n%2)?a:1 ) %mod;
    a = a * a % mod;
    n >>= 1;
  }
  return r;
}

int main(void){
    int n,k;cin>>n>>k;
    ll dp[k];
    rep1(i,k) dp[i]=modpow(k/i,n);
    ll res=0;
    for(int i=k;i>=1;i--){
        for(int j=2;i*j<=k;j++){
            dp[i]-=dp[i*j];
        }
        res+=dp[i]*i;
        res%=mod;
    }
    cout<<(mod+res)%mod<<endl;
}

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

#define         pb         push_back
#define         sf(x)      scanf("%d",&x)
#define         sfl(x)     scanf("%lld",&x)
#define         pf(x)      printf("%d\n",x)
#define         pfl(x)     printf("%lld\n",x)
#define         endl       '\n'
#define         pii        pair<int,int>
#define         mapii      map<int,int>
#define         mapll      map<ll,ll>
#define         mapci      map<char,int>
#define         mapcl      map<char,ll>
#define         mapsi      map<string,int>
#define         mapsl      map<string,ll>
#define         pll        pair<ll,ll>
#define         vi         vector<int>
#define         vl         vector<ll>
#define         vd         vector<double,double>
#define         all(c)     c.begin(),c.end()
#define         F          first
#define         S          second
#define         mp         make_pair
#define        ftc(x)      cerr << #x << ": " << x << " " << endl;
#define         PI         acos(-1)
#define         lcm(a,b)   ((a*b)/__gcd(a,b))
#define        optimize    ios_base::sync_with_stdio(false);cin.tie(NULL);
#define        sqr(a)       ((a)*(a))
#define         MOD    1000000007


inline void normal(ll &a) { a %= MOD; (a < 0) && (a += MOD); }
inline ll modMul(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a*b)%MOD; }
inline ll modAdd(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a+b)%MOD; }
inline ll modSub(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); a -= b; normal(a); return a; }
inline ll modPow(ll b, ll p) { ll r = 1; while(p) { if(p&1) r = modMul(r, b); b = modMul(b, b); p >>= 1; } return r; }
inline ll modInverse(ll a) { return modPow(a, MOD-2); }
inline ll modDiv(ll a, ll b) { return modMul(a, modInverse(b)); }

ll sol(ll A[], ll n, ll k)
{
	sort(A, A + n);

	ll res = 1;

	if (A[n - 1] == 0 && (k & 1))
		return 0;

	if (A[n - 1] <= 0 && (k & 1)) {
		for (ll i = n - 1; i >= n - k; i--)
			res = modMul(res,A[i]);
		return res;
	}

	ll i = 0;

	ll j = n - 1;


	if (k & 1) {
		res = modMul(res,A[j]);
		j--;
		k--;
	}

	k >>= 1ll;

	for (ll itr = 0; itr < k; itr++) {

		ll left_res = A[i] * A[i + 1];

		ll right_res = A[j] * A[j - 1];

		if (left_res > right_res) {
			res = modMul(res,left_res);
			i += 2;
		}
		else {
			res = modMul(res,right_res);
			j -= 2;
		}
	}

	return res;
}

int main()
{
	ll n,i,k,j,l,m;

	cin >> n >> k;

	ll ar[n+10];

	for(i=0;i<n;i++)cin >> ar[i];

	cout << sol(ar, n, k);

	return 0;
}


Measured memory_bytes: 5156
n = int(input())
table = [[False for i in range(13)] for j in range(4)]
marks = ['S', 'H', 'C', 'D']

for i in range(n):
    mark, num_s = input().split()
    num_index = int(num_s) - 1
    mark_index = marks.index(mark)
    table[mark_index][num_index] = True

for i in range(len(table)):
    for j in range(len(table[i])):
        if table[i][j] == False:
            print('%s %d' %(marks[i], j + 1))



Measured memory_bytes: 5604
#include<bits/stdc++.h>
using namespace std;
int main(){
  char a[15],b[15],c[15];
  cin >> a >> b >> c;  
  if(a[strlen(a)-1]==b[0]&&b[strlen(b)-1]==c[0]){
    cout << "YES"<< endl;
  }
  else{
    cout << "NO" << endl;
  }
}


Measured memory_bytes: 256
using System;
using System.Linq;

namespace _0360
{
    class Program
    {
        static void Main(string[] args)
        {
            bool[] used = new bool[1010];
            int[] x = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int n = int.Parse(Console.ReadLine());
            for (int i = 0; i < n; i++)
            {
                int[] a = Console.ReadLine().Split().Select(int.Parse).ToArray();
                for (int j = a[0]; j < a[1]; j++)
                {
                    used[j] = true;
                }
            }
            bool ret = true;
            for (int i = x[0]; i < x[1]; i++)
            {
                if (used[i]) ret = false;
            }
            Console.WriteLine(ret ? 0 : 1);
        }
    }
}

Measured memory_bytes: 9652
#include<bits/stdc++.h>
#define REP(x,y,z) for(int x=y;x<=z;x++)
#define MSET(x,y) memset(x,y,sizeof(x))
#define M 187
using namespace std;
int n,m;
int cnt[M][M];
int dp1[2][M][M][M]; //comp, x1, x2, y1 => y2
int dp2[2][M][M][M]; //comp, x1, y1, y2 => x2
int dp1y2[M][M][M]; //comp, x1, x2, y1 => y2 (horizon cut)
int dp2x2[M][M][M]; //comp, x1, y1, y2 => x2 (vertical cut)
char in[M][M];

int getcnt(int x1,int x2,int y1,int y2) {
    return cnt[x2][y2] - cnt[x1-1][y2] - cnt[x2][y1-1] + cnt[x1-1][y1-1];
}
int isfull(int x1,int x2,int y1,int y2) {
    int c = getcnt(x1,x2,y1,y2);
    return c==0 || (c==(x2-x1+1) * (y2-y1+1));
}
int main()
{
    while (~scanf("%d %d",&n,&m)) {
        MSET(dp1, 0);
        MSET(dp2, 0);
        MSET(cnt, 0);
        REP(i,1,n) scanf("%s", in[i]+1);

        //cnt
        REP(i,1,n) REP(j,1,m) {
            cnt[i][j] = cnt[i-1][j] + cnt[i][j-1] - cnt[i-1][j-1] + (in[i][j]=='#' ? 1 : 0);
        }

        int cur=1, fr=0, ans=32;
        //stage 0
        REP(x1,1,n)REP(x2,x1,n)REP(y1,1,m) {
            int y2 = max(dp1[fr][x1][x2][y1-1], y1-1);
            while (y2<m && isfull(x1,x2,y1,y2+1)) y2++;
            dp1[fr][x1][x2][y1] = y2;
        }
        REP(x1,1,n)REP(y1,1,m)REP(y2,y1,m) {
            int x2 = max(dp2[fr][x1-1][y1][y2], x1-1);
            while (x2<n && isfull(x1,x2+1,y1,y2)) x2++;
            dp2[fr][x1][y1][y2] = x2;
        }
        if (dp1[fr][1][n][1] >= m) ans = 0;

        REP(i,1,31) {
            if (ans<i) break;
            //dp1
            REP(x1,1,n)REP(x2,x1,n)REP(y1,1,m) {
                int y2 = dp1[fr][x1][x2][y1];
                if (y2<m) y2 = dp1[fr][x1][x2][y2+1];
                dp1[cur][x1][x2][y1] = y2;

                auto check = [&](int y) {
                    int x = dp2[fr][x1][y1][y];
                    if (x<n) x = dp2[fr][x+1][y1][y];
                    return x >= x2;
                };
                y2 = max(dp1y2[x1][x2][y1-1], y1-1);
                while (y2<m && check(y2+1)) y2++;
                dp1y2[x1][x2][y1] = y2;
                dp1[cur][x1][x2][y1] = max(dp1[cur][x1][x2][y1], y2);
            }

            //dp2
            REP(x1,1,n)REP(y1,1,m)REP(y2,y1,m) {
                int x2 = dp2[fr][x1][y1][y2];
                if (x2<n) x2 = dp2[fr][x2+1][y1][y2];
                dp2[cur][x1][y1][y2] = x2;

                auto check = [&](int x) {
                    int y = dp1[fr][x1][x][y1];
                    if (y<m) y = dp1[fr][x1][x][y+1];
                    return y >= y2;
                };
                x2 = max(dp2x2[x1-1][y1][y2], x1-1);
                while (x2<n && check(x2+1)) x2++;
                dp2x2[x1][y1][y2] = x2;
                dp2[cur][x1][y1][y2] = max(dp2[cur][x1][y1][y2], x2);
            }

            if (dp1[cur][1][n][1] >= m) ans = min(ans, i);

            swap(cur, fr);
            MSET(dp1y2, 0);
            MSET(dp2x2, 0);
        }
        printf("%d\n", ans);
    }
    
    return 0;
}



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

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> ii;
typedef tuple<ll, ll, ll> iii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define REP(i,n) for (ll i = 0; i < n; ++i)
#define REPR(i,n) for (ll i = n-1; i >= 0; --i)
#define FOR(i,m,n) for (int i = m; i < n; ++i)
#define FORR(i,m,n) for (ll i = n-1; i >= m; --i)
#define FORE(x,xs) for (const auto& x : xs)
#define PB push_back
#define MP make_pair
#define MT make_tuple
#define ALL(v) v.begin(), v.end()
#define rALL(v) v.rbegin(), v.rend()

int score(int n) {
    if (n == 1) return 300000;
    if (n == 2) return 200000;
    if (n == 3) return 100000;
    return 0;
}

int score2(int m, int n) {
    if (n == 1 && m == 1) return 400000;
    return 0;
}

int main() {
    int x, y;
    cin >> x >> y;
    cout << score(x) + score(y) + score2(x, y) << endl;
}

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

public class Solution
{
    public static void Main()
    {
        var N = int.Parse(Console.ReadLine());
        var A = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();

        var list = A.Select((x, i) => new { x, i = i + 1 }).OrderBy(a => a.x).Select(a => a.i).ToList();

        Console.WriteLine(string.Join(" ", list));
    }
}

Measured memory_bytes: 33756
import java.util.*

fun main() {
    val pw = java.io.PrintWriter(System.out)
    Problem.solve(Scanner(System.`in`), pw)
    pw.flush()
}

class FenwickTree(private val n: Int = 0) {
    private val data = LongArray(n)

    fun add(p: Int, x: Long) {
        var pp = p + 1
        while (pp <= n) {
            data[pp - 1] += x
            pp += pp and -pp
        }
    }

    fun sum(l: Int, r: Int): Long = sum(r) - sum(l)

    private fun sum(r: Int): Long {
        var s = 0L
        var rr = r
        while (rr > 0) {
            s += data[rr - 1]
            rr -= rr and -rr
        }
        return s
    }
}

object Problem {
    fun solve(sc: Scanner, pw: java.io.PrintWriter) {
        val N = sc.next().toInt()
        val Q = sc.next().toInt()
        val ft = FenwickTree(N)
        repeat(N) { i ->
            ft.add(i, sc.next().toLong())
        }
        repeat(Q) {
            if (sc.next().toInt() == 0) {
                val p = sc.next().toInt()
                val x = sc.next().toLong()
                ft.add(p, x)
            } else {
                val l = sc.next().toInt()
                val r = sc.next().toInt()
                pw.println(ft.sum(l, r))
            }
        }
    }
}


Measured memory_bytes: 69408
#define _USE_MATH_DEFINES
#define INF 0x3f3f3f3f
#include <cstdio>
#include <iostream>
#include <sstream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>
#include <list>
#include <cctype>
#include <utility>
 
using namespace std;
 
typedef long long ll;
typedef pair <int,int> P;
typedef pair <int,P > PP;
 
int tx[] = {0,1,1,0,-1,-1};
int ty[] = {1,1,0,-1,-1,0};
 
static const double EPS = 1e-8;

class State{
public:
  int mStep;
  int mX;
  int mY;
  State(int step,int x,int y) : mStep(step), mX(x), mY(y) {}
  bool operator <(const State& s) const{
    return mStep < s.mStep;
  }

  bool operator >(const State& s) const{
    return mStep > s.mStep;
  }
};

int CoundVisitedCell(map<P,int>& stage){
  int count = 0;
  for(int y=-30;y<=30;y++){
    for(int x=-30;x<=30;x++){
      if(stage.find(P(x,y)) == stage.end()) continue;
      if(stage[P(x,y)] >= 0) count++;
    }
  }
  return count;
}


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

    if(t==0 && n==0) break;

    map<P,int> stage;
    for(int i=0;i<n;i++){
      int x,y;
      scanf("%d %d",&x,&y);
      stage[P(x,y)] = -1;
    }

    int sx,sy;
    scanf("%d %d",&sx,&sy);

    priority_queue<State,vector<State>,greater<State> > que;
    que.push(State(0,sx,sy));
    stage[P(sx,sy)] = 0;

    int res = 0;
    while(!que.empty()){
      State s = que.top();
      que.pop();

      res++;
      if(s.mStep >= t) continue;

      for(int i=0;i<6;i++){
	int dx = s.mX + tx[i];
	int dy = s.mY + ty[i];

	//obstacle
	if(stage.find(P(dx,dy)) != stage.end()
	   && stage[P(dx,dy)] == -1) continue;

	//small step count is better
	if(stage.find(P(dx,dy)) != stage.end() 
	   && s.mStep+1 >= stage[P(dx,dy)] ) continue;

	stage[P(dx,dy)] = s.mStep+1;
	que.push(State(s.mStep+1,dx,dy));
      }
    }

    printf("%d\n",res);
  }
}

Measured memory_bytes: 1376
#include <iostream>
#include <string>
#include <algorithm>
#include <utility> 
#include <unordered_set>
#include <vector>
#include <list> 
#include <string>
#include <iterator> 
#include <deque>
#include <array>
#include <forward_list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#include <climits>
#include <bitset>
using namespace std;

#define N 20
#define EPS 1e-9
#define PI 3.14159265358979323846264338327950

int v[N], c[N];

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

	int n, ans, s1, s2;
	cin >> n;
	for (int i = 0; i < n; ++i)
		cin >> v[i];
	for (int i = 0; i < n; ++i)
		cin >> c[i];
	ans = 0;
	for (int mask = 1; mask <= (1<<n) - 1; ++mask) {
		s1 = s2 = 0;
		for (int i = 0; i < n; ++i) {
			if ((mask >> i) & 1) {
				s1 += v[i];
				s2 += c[i];
			}
		}
		ans = max(ans,s1 - s2);
	}
	cout << ans << '\n'; 
}


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

int main() {
	int N, M;
	string S, T;
	map<string, int> mp;
	cin >> N;
	for(N; N>0; --N){
	    cin >> S;
	    auto p = mp.find(S);
	    if(p!=mp.end()) ++mp[S];
	    else mp[S]=1;
	}
	cin >> M;
	for(M; M>0; --M){
	    cin >> T;
	    auto q = mp.find(T);
	    if(q!=mp.end()) --mp[T];
	}
	int Z=0;
	for(auto i=mp.begin(); i!=mp.end(); ++i) Z=max(Z, i->second);
	cout << Z << endl;
	return 0;
}

Measured memory_bytes: 256
n=int(input())
h=list(map(int,input().split()))
flag =True

for i in reversed(range(1,n)):
    if h[i-1]-h[i]>1:
        #print("No")
        flag = False
    elif h[i-1]-h[i]==1:
        h[i-1]-=1


if flag:
    print("Yes")
else:
    print("No")

    

Measured memory_bytes: 14396
#include <stdio.h>

int main(){

	int i,a,temp,x[2999],y[2999];

	for(i=0;i<=2999;i++){
		scanf("%d %d",&x[i],&y[i]);
		if(x[i]==0 && y[i]==0){ 
			a=i;
			break;
		}
	}

	for(i=0;i<a;i++){
		if(x[i]>y[i]){
			temp=x[i];
			x[i]=y[i];
			y[i]=temp;
		}
		printf("%d %d\n",x[i],y[i]);
	}
	
	return 0;
}

Measured memory_bytes: 624
N,K = map(int,input().split())
h = []
for i in range(N):
    h.append(int(input()))

h_diff = 999999999
h.sort()
for i in range(N-K+1):
    if h_diff > h[i+K-1] - h[i]:
        h_diff = h[i+K-1] - h[i]

print(h_diff)

Measured memory_bytes: 7384