akhauriyash/Code-Regression huggingface dataset:
let rec fix f x = f (fix f) x
let ans =
  Scanf.scanf "%d" @@ fun n ->
  let a = Array.init n (fun _ -> Scanf.scanf " %d" ((+) 0)) in
  let w0 =
    (0, min a.(0) a.(n-1) + 1) |> fix (fun f (l, r) ->
      if l+1 >= r then l else
        let m = (l+r) / 2 in
        let w = Array.fold_left (fun w h -> h - w) m a in
        if w < m then f (l, m) else f (m, r))
  in
  let wn, h' = Array.fold_left (fun (w, acc) h -> (h-w, (2*w)::acc)) (w0, []) a in
  List.rev h' |> List.iter (Printf.printf "%d ");
  print_newline ()
 

Measured memory_bytes: 8832
#include<iostream>
#include<cstdio>
#include <stdio.h>
#include<algorithm>
#include<cstring>
#include <string>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<map>
#include<vector>
#include<bits/stdc++.h>
#include <set>
#define ll   long long
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#define inf 0x3f3f3f3f3f3f3f3f
#define pi 3.1415926535898
#define N 200010
using namespace std;
struct A
{
    int x;
    int y;
}a[N];
char s[110][110];
int dp[110][110];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        scanf("%s",s[i]+1);
    }
    memset(dp,inf,sizeof(dp));
    dp[1][1]=(s[1][1]=='#');
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(s[i][j+1]=='.')
            {
                dp[i][j+1]=min(dp[i][j+1],dp[i][j]);
            }
            else
            {
                dp[i][j+1]=min(dp[i][j+1],dp[i][j]+(s[i][j]=='.'));
            }
            if(s[i+1][j]=='.')
            {
                dp[i+1][j]=min(dp[i+1][j],dp[i][j]);
            }
            else
            {
                dp[i+1][j]=min(dp[i+1][j],dp[i][j]+(s[i][j]=='.'));
            }
        }
    }
    cout<<dp[n][m]<<endl;
    return 0;
}


Measured memory_bytes: 3812
#include <bits/stdc++.h>
#define REP(i,a,b) for(int(i)=(a);(i)<(b);++(i))
#define RREP(i,a,b) for(int(i)=(a)-1;(i)>=(b);--(i))
#define ALL(x) (x).begin(),(x).end()
#define chmin(x,v) x = min(x, v)
#define chmax(x,v) x = max(x, v)
using namespace std;
typedef long long ll;

int a[] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};

int main()
{
  int K;
  cin >> K;
  cout << a[K-1] << endl;

  return 0;
}


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

using namespace std;

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

  int N, M; cin>>N>>M;
  vector<vector<int>> graph(N);
  for (int i = 0; i < M; i++) {
	int a, b; cin>>a>>b;
	a--; b--;
	graph[a].push_back(b);
  }
  auto find_circuit = [&, f=[&](auto g, int root, int c, vector<bool>& visited) -> unordered_set<int> {
    if (visited[c]) {
	  unordered_set<int> res;
	  for (int i = 0; i < N; i++) {
		if (visited[i]) {
		  res.insert(i);
		}
	  }
	  return res;
    }
	visited[c] = true;
	for (auto t : graph[c]) {
	  auto res = g(g, root, t, visited);
	  if (not res.empty()) {
	    return res;
	  }
	}
	visited[c] = false;
	return {};
  }](int root) {
    vector<bool> visited(N, false);
	return f(f, root, root, visited);
  };

  auto make_graph = [&](unordered_set<int>& route) {
	vector<vector<int>> ngraph(N);
	for (auto s : route) {
	  for (auto t : graph[s]) {
		if (route.count(t)) {
		  ngraph[s].push_back(t);
		}
	  }
	}
	return ngraph;
  };

  unordered_set<int> route;
  for (int i = 0; i < N; i++) {
	route = find_circuit(i);
	if (not route.empty()) {
	  break;
	}
  }
  if (route.empty()) {
    cout << -1 << endl;
    return 0;
  }

  while (true) {
	graph = make_graph(route);
	int r = -1;
	{
	  // Find vertex more than 2 in-degrees.
	  unordered_set<int> in;
	  for (auto s : route) {
		for (auto t : graph[s]) {
		  if (in.count(t)) {
			r = t;
			break;
		  }
		  in.insert(t);
		}
		if (r != -1)
		  break;
	  }
	}
	if (r == -1) {
	  break;
	}
	set<int> from;
	for (auto s : route) {
	  for (auto t : graph[s]) {
	    if (t == r)
	      from.insert(s);
	  }
	}

	route = {r};
	int c = r;
	while (from.count(c) == 0) {
	  c = graph[c].front();
	  route.insert(c);
	}
  }
  cout << route.size() << endl;
  for (auto s : route)
	cout << s+1 << endl;

  return 0;
}


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


int main() {
  string s;
  int n;
  cin >> n >> s;
  rep(i,s.length()) {
    int a = s[i] - 'A';
    a = (a + n) % 26;
    char str = 'A' + a;
    cout << str;
  }
  cout << endl;
  return 0;
}

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

vector<int> dx = {1, 1, 1, -1, -1, -1, 0, 0}, dy = {1, -1, 0, 1, -1, 0, 1, -1};
int w, h;
vector<vector<bool>> field;

void dfs(int x, int y)
{
  field.at(y).at(x) = false;
  rep(direction, 8)
  {
    int nx = x + dx.at(direction), ny = y + dy.at(direction);
    if (0 <= nx && nx < w && 0 <= ny && ny < h && field.at(ny).at(nx))
    {
      dfs(nx, ny);
    }
  }
}

int main()
{
  while (1)
  {
    cin >> w >> h;
    if (!w && !h)
    {
      break;
    }
    field.resize(h, vector<bool>(w));
    field.assign(h, vector<bool>(w, false));
    rep(y, h)
    {
      rep(x, w)
      {
        int c;
        cin >> c;
        if (c)
        {
          field.at(y).at(x) = true;
        }
      }
    }
    int ans = 0;
    rep(y, h)
    {
      rep(x, w)
      {
        if (field.at(y).at(x))
        {
          dfs(x, y);
          ans++;
        }
      }
    }
    cout << ans << endl;
  }
}


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

//#define int long long
//struct Fast {Fast(){cin.tie(0);ios::sync_with_stdio(0);}} fast;
//const int MOD = 1e9 + 7;
using intpair = pair<int, int>;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define reps(i, n, m) for (int i = (int)(n); i <= (int)(m); i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define ceiv(a, b) ((int)((a) + (b) - 1)/(int)(b))

int dp[1001][1001];

inline bool chmax(int &a, int b){
    if(a < b) a = b;
    return a < b;
}

signed main() {
    int Q; cin >> Q;
    while(Q--){
        string s, t;
        cin >> s >> t;
        int n = (int)s.length();
        int m = (int)t.length();
        
        rep(i,n+1)rep(j,m+1) dp[i][j] = 0;
        
        reps(i,1,n)reps(j,1,m){
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            if(s[i-1] == t[j-1]){
                chmax(dp[i][j], dp[i-1][j-1]+1);
            }
        }
        
        cout << dp[n][m] << endl;
    }
}


Measured memory_bytes: 7004
#include<iostream>

using namespace std;

char c[100][100];

int main()
{
	int H, W;
	cin >> H >> W;
	for (int h = 0; h < H; h++)
	{
		for (int w = 0; w < W; w++)
		{
			cin >> c[h][w];
		}
	}

	for (int i = 0; i < (W + 2); i++)
		cout << "#";
	cout << "" << endl;

	for (int h = 0; h < H; h++)
	{
		cout << "#";
		for (int w = 0; w < W; w++)
		{
			cout << c[h][w];
		}
		cout << "#" << endl;
	}

	for (int i = 0; i < (W + 2); i++)
		cout << "#";
	cout << "" << endl;

	return 0;
}

Measured memory_bytes: 256
/*

                   _ooOoo_
                  o8888888o
                  88" . "88
                  (| -_- |)
                  O\  =  /O
               ____/`---'\____
             .'  \\|     |//  `.
            /  \\|||  :  |||//  \
           /  _||||| -:- |||||-  \
           |   | \\\  -  /// |   |
           | \_|  ''\---/''  |   |
           \  .-\__  `-`  ___/-. /
         ___`. .'  /--.--\  `. . __
      ."" '<  `.___\_<|>_/___.'  >'"".
     | | :  `- \`.;`\ _ /`;.`/ - ` : | |
     \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
                   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
                    prayer
*/

// g++ -std=c++11 a.cpp
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<unordered_map>
#include<utility>
#include<cmath>
#include<random>
#include<cstring>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#include<typeinfo>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define FOR(i,a) for(auto i:a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
#define show1d(v) rep(_,v.size())cout<<" "<<v[_];cout<<endl;
#define show2d(v) rep(__,v.size()){rep(_,v[__].size())cout<<" "<<v[__][_];cout<<endl;}
using namespace std;
//kaewasuretyuui
typedef long long ll;
#define int ll
typedef int Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
// #define mt make_tuple
// typedef tuple<int,int,int> tp;
// typedef vector<tp> vt;
template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;}
template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;}
//template<class C>constexpr int size(const C &c){return (int)c.size();}
//template<class T,size_t N> constexpr int size(const T (&xs)[N])noexcept{return (int)N;}
const double PI=acos(-1);
const double EPS=1e-9;
Def inf = sizeof(Def) == sizeof(long long) ? 2e18 : 1e9+10;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};

signed main(){
	int a,b;
	cin>>a>>b;
	cout<<a+b/2<<endl;
}















Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#define int long long
#define double long double
using namespace std;

const int INF = 1e+18;
int n, a, b;
int v[50];
int max_dp[51][51];
int num_dp[51][51];

signed main() {
	int i, j;
	
	cin >> n >> a >> b;
	for (i = 0; i < n; i++) cin >> v[i];
	
	for (i = 0; i <= n; i++) {
		for (j = 0; j <= n; j++) {
			max_dp[i][j] = -INF;
			num_dp[i][j] = 0;
		}
	}
	
	max_dp[0][0] = 0;
	for (i = 0; i < n; i++) {
		for (j = 0; j <= i; j++) {
			max_dp[i + 1][j] = max(max_dp[i][j], max_dp[i + 1][j]);
			max_dp[i + 1][j + 1] = max(max_dp[i][j] + v[i], max_dp[i + 1][j + 1]);
		}
	}
	
	num_dp[0][0] = 1;
	for (i = 0; i < n; i++) {
		for (j = 0; j <= i; j++) {
			if (max_dp[i][j] == max_dp[i + 1][j]) {
				num_dp[i + 1][j] += num_dp[i][j];
			}
			if (max_dp[i][j] + v[i] == max_dp[i + 1][j + 1]) {
				num_dp[i + 1][j + 1] += num_dp[i][j];
			}
		}
	}
	
	double ans1 = 0;
	int ans2 = 0;
	
	for (i = a; i <= b; i++) {
		double ave = (double)max_dp[n][i] / i;
		if (ans1 < ave) {
			ans1 = ave;
		}
	}
	
	for (i = a; i <= b; i++) {
		double ave = (double)max_dp[n][i] / i;
		if (ans1 == ave) {
			ans2 += num_dp[n][i];
		}
	}
	
	printf("%.14Lf\n", ans1);
	printf("%lld\n", ans2);
	return 0;
}

Measured memory_bytes: 256
def test_case():
    n = int(input())
    n_list = list(map(int, input().split()))
    n_min, n_max, n_sum = 0, 0, 0
    for i in range(n):
        if n_min == 0:
            n_min = n_list[i]
        elif n_min > n_list[i]:
            n_min = n_list[i]

        if n_max == 0:
            n_max = n_list[i]
        elif n_max < n_list[i]:
            n_max = n_list[i]

        n_sum += n_list[i]
    print(n_min, n_max, n_sum)


if __name__ == "__main__":
    test_case()


Measured memory_bytes: 6596
def abc():
    a, b = map(int, input().split())

    if a % 3 == 0:
        print('Possible')
        return
    if b % 3 == 0:
        print('Possible')
        return
    if (a + b) % 3 == 0:
        print('Possible')
        return
    print('Impossible')


abc()


Measured memory_bytes: 2940
def solve():
    import bisect
    S = input()
    T = input()
    dic = {}
    length = {}

    for i, s in enumerate(S, 1):
        if s not in dic:
            dic[s] = []
        dic[s].append(i)

    for k, v in dic.items():
        if k not in length:
            length[k] = 0
        length[k] = len(v)

    l, turn, prov = len(S), 0, 0

    for t in T:
        if t not in dic:
            print(-1)
            exit()
        x = bisect.bisect(dic[t], prov)
        if x < length[t]:
            prov = dic[t][x]
        else:
            turn += 1
            prov = dic[t][0]
    print(turn * l + prov)

solve()



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

int dp[100005][5];

int main() {
	int n; cin >> n;
	vector<int> a(n + 1), b(n + 1), c(n + 1);
	for (int i = 1; i <= n; i++) {
		cin >> a[i] >> b[i] >> c[i];
	}
	dp[1][1] = a[1];
	dp[1][2] = b[1];
	dp[1][3] = c[1];
	for (int i = 2; i <= n; i++) {
		dp[i][1] = max(dp[i - 2][1], max(dp[i - 1][2], dp[i - 1][3])) + a[i];
		dp[i][2] = max(dp[i - 2][2], max(dp[i - 1][1], dp[i - 1][3])) + b[i];
		dp[i][3] = max(dp[i - 2][3], max(dp[i - 1][1], dp[i - 1][2])) + c[i];
	}
	cout << max(max(dp[n][1], dp[n][2]), dp[n][3]) << '\n';
}

Measured memory_bytes: 3328
#include "bits/stdc++.h"
using namespace std;
const int MAX = 700000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}

// 二項係数計算
long long COM(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
/*第二引数で第一引数を割ったときの切り上げの計算*/
long long int maxtime(long long int x, long long int y) {
	return(x + y - 1) / y;

}
/*最大公約数*/
long long int lcm(long long int number1, long long int number2) {
	long long int m = number1;
	long long int n = number2;

	if (number2 > number1) {
		m = number2;
		n = number1;
	}
	long long int s = -1;
	while (s != 0) {
		s = m % n;
		m = n;
		n = s;
	}
	return m;
}
/*最大公倍数*/
long long int gcd(long long int number1, long long int number2) {
	long long int m = number1;
	long long int n = number2;
	return m / lcm(m, n) * n;
}
long long int dp[100020] = {};
int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= 50000; i++) {
		double s = i;
		double ans = s * 1.08;
		int anss = ans / 1;
		if (anss == n) {
			cout << i;
			return 0;
		}
	}
	cout << ":(";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
bool ok(string s)
{
    static bool vis[11];
    memset(vis,0,sizeof vis);
    int num = 0;
    char big = 'a';
    char small = 'z';
    for(char c:s)
    {
        if(!vis[c-'a'])
        {
            vis[c-'a'] = 1;
            num++;
        }
        big = max(big,c);
        small = min(small,c);
    }
    return small == 'a' && big - 'a' + 1 == num;
}
bool next(string& s)
{
    for(int i=s.size()-1;i>=0;--i)
    {
        string tmp = s;
        tmp[i]++;
        for(int j=i+1;j<s.size();++j)tmp[j]='a';
        if(ok(tmp)) {
            s = tmp;
            return true;
        }
    }
    return false;
}
void solve(ll N)
{
    string s;
    for(int i=0;i<N;++i)s+='a';
    string t;
    for(int i=0;i<N;++i)t+='a'+i;
    cout<<s<<endl;
    while(s!=t){
        next(s);
        cout<<s<<endl;
    }
}


int main()
{
    ll N;
    cin >> N;
    solve(N);
    return 0;
}


Measured memory_bytes: 1536
#include <iostream>
#include <sstream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <bitset>
#include <assert.h>
#include <deque>
using namespace std;

typedef unsigned long long UL;
typedef long long LL;
typedef long double LD;
#define LP(i, a, b) for (int i = int(a); i < int(b); i++)
#define LPE(i, a, b) for (int i = int(a); i <= int(b); i++)
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef vector<vector<PII> > WAL;
typedef vector<vector<int> > SAL;
#define Ep 1e-8
#define INF 1e9
#define LINF 1e18

int const MaxSize = 1e5 + 5;
LL const MOD = 1e9 + 7;
LL const BASE = 256;

/*
 */
int N;
string S;
LL cnt[26];

int main() {
	ios_base::sync_with_stdio(false);
	//freopen("/Users/georgeli/A_1.in", "r", stdin);
	cin >> N >> S;
	LP(i, 0, N){
		cnt[S[i] - 'a']++;
	}

	LL ans = 1;

	LP(i, 0, 26){

		ans *= (cnt[i] + (LL)1);
		ans %= MOD;
	}
	ans--;

	cout << ans;

	return 0;
}


Measured memory_bytes: 512
#include <iostream>
#include <cmath>

using namespace std;
long long n, k;
long long A[100001];
long long F[100001];

void input()
{
    cin>>n>>k;
    for(long long i=1; i<=n; i++) cin>>A[i];
}

int main()
{
    input();
    if(k>n) k=n;
    F[1]=0;
    F[2]=abs(A[1]-A[2]);
    for(long long i=3; i<=k; i++)
    {
        F[i]=999999999;
        for(long long j=1; j<=i-1; j++)
        {
            long long tmp=F[j]+abs(A[i]-A[j]);
            F[i]=min(F[i],tmp);
        }
    }
    for(long long i=k+1; i<=n; i++)
    {
        F[i]=999999999;
        for(long long j=i-k; j<=i-1; j++)
        {
            long long tmp=F[j]+abs(A[i]-A[j]);
            F[i]=min(F[i],tmp);
        }
    }
    cout<<F[n];
    return 0;
}


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

const int MOD=998244353;
const int INF=0x3f3f3f3f;
const ll INFL=0x3f3f3f3f3f3f3f3f;

ll dp[5000][5000];

int main(){
	int a,b,c,d;cin>>a>>b>>c>>d;
	dp[a][b]=1;
	for(int i=a;i<c;i++){
		ll sum=0;
		for(int j=b;j<=d;j++){
			(dp[i+1][j]+=dp[i][j]*j)%=MOD;
			(dp[i+1][j]+=sum)%=MOD;
			(sum+=dp[i][j])%=MOD;
			(sum*=i)%=MOD;
		}
	}
	ll ans=0;
	ll D=1;
	for(int j=d;j>=b;j--){
		(ans+=dp[c][j]*D)%=MOD;
		(D*=c)%=MOD;
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 85880
#include <math.h>
#include <stdio.h>

int rel_l_l( double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4 ) {
	int rel;

	rel = 0;
	if ( fabs( ( x1 - x2 ) * ( x3 - x4 ) + ( y1 - y2 ) * ( y3 - y4 ) ) < 1e-10 )
		rel = 1;
	else if ( fabs( ( x1 - x2 ) * ( y3 - y4 ) - ( y1 - y2 ) * ( x3 - x4 ) ) < 1e-10 ) {
		rel = 2;
		if ( fabs( ( x1 - x3 ) * ( y3 - y4 ) - ( y1 - y3 ) * ( x3 - x4 ) ) < 1e-10 )
			rel = 3;
	}

	return rel;
}

int main( void ) {
	int n;
	scanf( "%d", &n );
	while ( n-- ) {
		int rel;
		double x1, y1, x2, y2, x3, y3, x4, y4;

		scanf( "%lf %lf %lf %lf %lf %lf %lf %lf", &x1, &y1, &x2, &y2, &x3, &y3, &x4, &y4 );
		
		rel = rel_l_l( x1, y1, x2, y2, x3, y3, x4, y4 );
		puts( rel == 2 || rel == 3 ? "YES" : "NO" );
	}

	return 0;
}

Measured memory_bytes: 620
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>

using namespace std;

int main()
{
    int a,b,c;
    scanf("%d%d%d",&a,&b,&c);
    if (a+b>=c) printf("Yes\n");
    else printf("No\n");
    return 0;
}


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

int main() {
  int A,B; cin>> A >> B;
  bool f = false;
  for ( int i = 1; i <= 3; i++ ) {
    int ans = A * B * i;
    if ( ans % 2 == 1 ) f = true;
    
  }

  if (f) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long int

using namespace std;

const ll mod=1000000007;
const ll inf=1e18;

int main(){

  ll h,w,k;
  cin >> h >> w >> k;
  char c[h][w];
  ll s=0;
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      cin >> c[i][j];
      if(c[i][j]=='#')s++;
    }
  }
  
  ll l=0;

  for(int b=0;b<(1<<h);b++){
    for(int d=0;d<(1<<w);d++){
        vector<int> v={},u={};
        ll m=s;
        for(int i=0;i<h;i++){
            if(b&(1<<i))v.push_back(i);
        }
        for(int i=0;i<w;i++){
            if(d&(1<<i))u.push_back(i);
        }
        //if(b==0 && d==5)cout << u[0] << " "<<u[1] << endl; 
        char e[h][w];
        for(int i=0;i<h;i++){
          for(int j=0;j<w;j++)e[i][j]=c[i][j];
        }
        for(int i=0;i<v.size();i++){
          for(int j=0;j<w;j++){
            if(e[v[i]][j]=='#'){
              e[v[i]][j]='r';
              m--;
            }
            if(e[v[i]][j]=='.')e[v[i]][j]='r';
          }
        }
        for(int j=0;j<u.size();j++){
          for(int i=0;i<h;i++){
            if(e[i][u[j]]=='#'){
              e[i][u[j]]='r';
              m--;
              //if(b==0 && d==5)cout << i << " " <<j << endl;
            }
            if(e[i][u[j]]=='.')e[i][u[j]]='r';
          }
        }
        if(m==k)l++;
        //if(b==0 && d==5)cout << v.size() << endl;
        //if(m==k)cout << b << " " << d << endl;
    }
    }

  cout << l << endl;

}

Measured memory_bytes: 3608
#include<bits/stdc++.h>
using namespace std;
int find(int x);
int same(int x,int y);
void unite(int x,int y);
int p[100009];
int cnt[100009];

int main(){
  int n,m;
  cin>>n>>m;
  for(int i=0;i<=n;i++)p[i]=i;
  for(int i=0;i<m;i++){
    int x,y,z;
    cin>>x>>y>>z;
    if(!same(x,y))unite(x,y);
  }
  for(int i=1;i<=n;i++){
    find(i);
    cnt[p[i]]++;
  }
  int ans=0;
  for(int i=1;i<=n;i++){
    if(cnt[i]>0)ans++;
  }
  cout<<ans<<endl;
  return(0);
}

int find(int x){
  if(p[x]==x)return x;
  return p[x]=find(p[x]);
}

int same(int x,int y){
  if(find(x)==find(y))return 1;
  return 0;
}

void unite(int x,int y){
  x=find(x);
  y=find(y);
  p[x]=y;
}



Measured memory_bytes: 1152
#include<bits/stdc++.h>
using namespace std;
int main(){
  int a,b;
  cin>>a>>b;
  for(int i=1;i<=10000;i++){
    int a2=i*8/100;
    int b2=i/10;
    if(a2==a&&b2==b){
      cout<<i;
      return 0;
    }
  }
  cout<<-1;
  return 0;
}

Measured memory_bytes: 3596
import java.io.BufferedReader;
import java.io.Closeable;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
		
	public static void main(String[] args) throws IOException {
		final Scanner sc = new Scanner(System.in);
		
		final int N = sc.nextInt();
		long[] array = new long[N];
		for(int i = 0; i < N; i++){
			array[i] = sc.nextLong();
		}
		
		HashMap<Long, Integer> counts  = new HashMap<Long, Integer>();
		HashMap<Long, Integer> indexes = new HashMap<Long, Integer>();
		for(int i = 0; i < N; i++){
			if(!indexes.containsKey(array[i])){
				indexes.put(array[i], i);
			}
			
			if(!counts.containsKey(array[i])){
				counts.put(array[i], 0);
			}
			counts.put(array[i], counts.get(array[i]) + 1);
		}
		
		long count = 0;
		long[] answer = new long[N + 1];
		
		PriorityQueue<Long> queue = new PriorityQueue<Long>(Collections.reverseOrder());
		queue.addAll(counts.keySet());
		
		while(!queue.isEmpty()){
			final long curr_value = queue.poll();
			final long curr_count = counts.get(curr_value);
			final int curr_index = indexes.get(curr_value);
			//System.out.println(curr_value + " " + curr_count + " " + curr_index);
			
			final long next_value = queue.isEmpty() ? 0 : queue.peek();
			final long do_move = (count + curr_count) * (curr_value - next_value);
				
			answer[curr_index] += do_move;
			count += curr_count;
			
			if(next_value != 0){
				final int next_index = indexes.get(next_value);
				indexes.put(next_value, (Math.min(next_index, curr_index)));
			}
		}
		
		for(int i = 0; i < N; i++){
			System.out.println(answer[i]);
		}
	}
	
	public static class Scanner implements Closeable {
		private BufferedReader br;
		private StringTokenizer tok;
 
		public Scanner(InputStream is) throws IOException {
			br = new BufferedReader(new InputStreamReader(is));
		}
 
		private void getLine() throws IOException {
			while (!hasNext()) {
				tok = new StringTokenizer(br.readLine());
			}
		}
 
		private boolean hasNext() {
			return tok != null && tok.hasMoreTokens();
		}
 
		public String next() throws IOException {
			getLine();
			return tok.nextToken();
		}
 
		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}
 
		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}
 
		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}
		
		public int[] nextIntArray(int n) throws IOException {
			final int[] ret = new int[n];
			for(int i = 0; i < n; i++){
				ret[i] = this.nextInt();
			}
			return ret;
		}
		
		public long[] nextLongArray(int n) throws IOException {
			final long[] ret = new long[n];
			for(int i = 0; i < n; i++){
				ret[i] = this.nextLong();
			}
			return ret;
		}
 
		public void close() throws IOException {
			br.close();
		}
	}
}

Measured memory_bytes: 73604
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        String[] S = new String[N+1];
        for (int i = 0; i < N+1; i++) {
            S[i] = sc.nextLine();
        }
        int C0 = 0;
        int C1 = 0;
        int C2 = 0;
        int C3 = 0;
        int ER = 0;
        for (int i = 0; i < N+1; i++) {
            if ( S[i].equals("AC")) {
                C0 = C0 + 1;
            } else if ( S[i].equals("WA")) {
                C1 = C1 + 1;
            } else if ( S[i].equals("TLE")) {
                C2 = C2 + 1;
            } else if (S[i].equals("RE")){
                C3 = C3 + 1;
            } else {
                ER = 0;
            }
        }
        System.out.println("AC" + " " + "x" + " " + C0);
        System.out.println("WA" + " " + "x" + " " + C1);
        System.out.println("TLE" + " " + "x" + " " + C2);
        System.out.println("RE" + " " + "x" + " " + C3);
    }
}

Measured memory_bytes: 65072
//Let's join Kaede Takagaki Fan Club !!
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
#define all(x) x.begin(),x.end()
template<class T>
void dmp(T a){
	rep(i,a.size()) cout << a[i] << " ";
	cout << endl;
}
template<class T>
bool chmax(T&a, T b){
	if(a < b){
		a = b;
		return 1;
	}
	return 0;
}
template<class T>
bool chmin(T&a, T b){
	if(a > b){
		a = b;
		return 1;
	}
	return 0;
}
template<class T>
void g(T &a){
	cin >> a;
}
template<class T>
void o(const T &a,bool space=false){
	cout << a << (space?' ':'\n');
}
//ios::sync_with_stdio(false);
const ll mod = 1000000007;//998244353
template<class T>
void add(T&a,T b){
	a+=b;
	if(a >= mod) a-=mod;
}
struct UF{
	int par[2000005],ran[2000005];
	void init(){ for(int i=0;i<2000005;i++) par[i] = i, ran[i] = 0; }
	int find(int x){ if(x == par[x]) return x; else return par[x] = find(par[x]); }
	void unite(int x,int y){
		x = find(x); y = find(y); if(x==y) return;
		if(ran[x] < ran[y]) par[x] = y;
		else{
			par[y] = x;
			if(ran[x] == ran[y]) ran[x]++;
		}
	}
	bool same(int x,int y){ return find(x)==find(y); }
}uf;


ll modpow(ll x,ll n){
	ll res=1;
	while(n>0){
		if(n&1) res=res*x%mod;
		x=x*x%mod;
		n>>=1;
	}
	return res;
}
ll F[2000005],R[2000005];
void make(){
	F[0] = 1;
	for(int i=1;i<2000005;i++) F[i] = F[i-1]*i%mod;
	R[2000004] = modpow(F[2000004], mod-2);
	for(int i=2000003;i>=0;i--) R[i] = R[i+1] * (i+1) % mod;
}
ll C(int a,int b){
	return F[a]*R[b]%mod*R[a-b]%mod;
}
void solve(){
	int n; cin >> n;
	n = (n+999)/1000 * 1000 - n;
	cout << n << endl;
}




int main(){
	uf.init();
	make();
	solve();
}

Measured memory_bytes: 50500
#include <iostream>
#include<bits/stdc++.h>
#include <stdio.h>
#include <stdlib.h>

using namespace std;

int main()
{
    int n, k;
    cin >> n >> k;
    int counter = 0;
    for(int i = 0; i < n ; i++){
        int x;
        cin >> x;
        if(x >= k)
            counter++;
    }
    printf("%d", counter);

    return 0;
}


Measured memory_bytes: 256
/*{{{*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<iostream>
#include<sstream>
#include<set>
#include<map>
#include<queue>
#include<bitset>
#include<vector>
#include<limits.h>
#include<assert.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define FOR(I, A, B) for (int I = (A); I <= (B); ++I)
#define FORS(I, S) for (int I = 0; S[I]; ++I)
#define RS(X) scanf("%s", (X))
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define CASET int ___T; scanf("%d", &___T); for(int cs=1;cs<=___T;cs++)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<PII> VPII;
typedef pair<LL,LL> PLL;
typedef vector<PLL> VPLL;
template<class T> void _R(T &x) { cin >> x; }
void _R(int &x) { scanf("%d", &x); }
void _R(LL &x) { scanf("%lld", &x); }
void _R(double &x) { scanf("%lf", &x); }
void _R(char &x) { scanf(" %c", &x); }
void _R(char *x) { scanf("%s", x); }
void R() {}
template<class T, class... U> void R(T &head, U &... tail) { _R(head); R(tail...); }
template<class T> void _W(const T &x) { cout << x; }
void _W(const int &x) { printf("%d", x); }
void _W(const LL &x) { printf("%lld", x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
template<class T,class U> void _W(const pair<T,U> &x) {_W(x.F); putchar(' '); _W(x.S);}
template<class T> void _W(const vector<T> &x) { for (auto i = x.begin(); i != x.end(); _W(*i++)) if (i != x.cbegin()) putchar(' '); }
void W() {}
template<class T, class... U> void W(const T &head, const U &... tail) { _W(head); putchar(sizeof...(tail) ? ' ' : '\n'); W(tail...); }
#ifdef HOME
 #define DEBUG(...) {printf("# ");printf(__VA_ARGS__);puts("");}
#else
 #define DEBUG(...)
#endif
int MOD = 1e9+7;
void ADD(LL& x,LL v){x=(x+v)%MOD;if(x<0)x+=MOD;}
/*}}}*/
const int SIZE = 1e6+10;
char s[SIZE];
int main(){
    RS(s);
    int n=LEN(s);
    int now=0;
    int an=0;
    for(int i=n-1;i>=0;i--){
        now+=s[i]-'0';
        if(now>5){
            an+=10-now;
            now=1;
        }
        else if(now<5){
            an+=now;
            now=0;
        }
        else{
            an+=5;
            if(i&&s[i-1]>='5'){
                now=1;
            }
            else now=0;
        }
    }
    W(an+now);
    return 0;
}


Measured memory_bytes: 1280
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=1000000007,MAX=100003,INF=1<<30;

int main(){
    
    int N;cin>>N;
    double sum=0.0;
    for(int i=0;i<N;i++){
        double a;cin>>a;
        sum+=(1.0)/a;
    }
    cout<<setprecision(25)<<1.0/sum<<endl;
}




Measured memory_bytes: 256
m=10**9+7
f=max
for _ in range(int(input())):
	x,y=sorted(map(int,input().split()))
	s=-1
	i=j=1
	while j<=x and i+j<=y:
		i,j=j,i+j
		s+=1
	if x==1 or y<3:print(1,x*y%m)
	else:
		a=max(0,(y-j)//i+1)+f(0,(x-j)//i+1)
		i=j=1
		for c in range(s):
			k,l=j,i+j*2
			for _ in range(s-c):k,l=l,k+l
			if x>=k:a+=f(0,(y-l)//k+1)
			if y>=k:a+=f(0,(x-l)//k+1)
			i,j=j,i+j
		print(s+1,a%m)

Measured memory_bytes: 80428
#include <bits/stdc++.h>
using namespace std;
#define modulo 1000000007
#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)
#define Inf 1000000000


int main(){
	
	int N,P;
	cin>>N>>P;
	
	int odd = 0,even = 0;
	
	for(int i=0;i<N;i++){
		int A;
		cin>>A;
		
		if(A%2==0)even++;
		else odd++;
	}
	
	long long ans = 1;
	
	ans *= ((long long)1<<even);
	
	if(odd==0){
		if(P==1)ans=0;
	}
	else{
		ans *= ((long long)1<<(odd-1));
	}
	
	cout<<ans<<endl;
	
	return 0;
}

Measured memory_bytes: 256
import java.util.*;
class Main {
	public static void main(String...args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int m = scan.nextInt();
		int l = scan.nextInt();
		int[][] A = new int[n][m];
		int[][] B = new int[m][l];
		long[][] C = new long[n][l];
		
		//input
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++) {
				A[i][j] = scan.nextInt();
			}
		}
		for(int i = 0; i < m; i++) {
			for(int j = 0; j < l; j++) {
				B[i][j] = scan.nextInt();
			}
		}
		for(int v = 0; v < n; v++) {
			for(int h = 0; h < l; h++) {
				for(int k = 0; k < m; k++) {
					C[v][h] += A[v][k] * B[k][h];
				}
			}
		}
		//output
		for(int v = 0; v < n; v++) {
			for(int h = 0; h < l; h++) {
				if(h != l-1) {
					System.out.print(C[v][h] + " ");
				} else {
					System.out.println(C[v][h]);
				}
			}
		}
	}
}


Measured memory_bytes: 53800
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<bool> vb;
#define pb push_back
#define fi first
#define se second
#define in insert
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int mod = 1e9 + 7;
const int N = 2e5 + 5;
vi adj[N];
int n;
void solve(){
    int m;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int x, y;
        cin >> x >> y;
        adj[x].pb(y);
        adj[y].pb(x);
    }
    unordered_map<int, bool> is;
    for (int to : adj[n]) {
        is[to] = true;
    }
    for (int f : adj[1]) {
        if (is[f]) {
            cout << "POSSIBLE";
            return;
        }
    }
    cout << "IMPOSSIBLE";
}
int main(){
    speed;
    int t = 1;
    //cin >> t;
    for (int i = 1; i <= t; ++i) {
        solve();
    }
}

Measured memory_bytes: 20268
#include <iostream>
#include <utility>
#include <stdint.h>

using namespace std;

int main()
{
  int M1,D1,M2,D2;
  cin >> M1 >> D1;
  cin >> M2 >> D2;

  cout << (M1!=M2?1:0) << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <vector>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <deque>
#include <algorithm>
#include <math.h>
#include <random>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define int long long
#define double long double
#define Matrix vector<vector<int> >
#define kektor vector
#define pp pair
#define all(x) x.begin(), x.end()

using namespace std;

typedef long long ll;

int RandInt(int min, int max) {
    if (max < min) {
        swap(min, max);
    }
    random_device rd;
    mt19937 mt(rd());
    uniform_int_distribution<int> dist(min, max);
    return dist(mt);
}

struct Node {
	int l, r, x; 
	Node(int _l, int _r, int _x) : l(_l), r(_r), x(_x) {} 
	Node() : l(-1), r(-1), x(0) {} 
};

const int maxn = 2e5 + 1, mod = 1e9;
bool debug = false;
int n, m, all = 0; 
vector<vector<char> > gr;
vector<int> x = {0, 0, 1, -1};
vector<int> y = {-1, 1, 0, 0};
vector<vector<int> > dist;

bool check(int x, int y) {
	return x >= 0 && x < m && y >= 0 && y < n;
}

void bfs() {
	deque<pair<int, int> > q; 
	q.pb({0, 0}); 
	dist[0][0] = 0;
	while (q.size()) {
		pair<int, int> el = q.front(); 
		q.pop_front();
		for (int i = 0; i < 4; ++i)  {
			pair<int, int> el1 = {el.ff + x[i], el.ss + y[i]}; 
			if (check(el1.ff, el1.ss) && gr[el1.ss][el1.ff] == '.' && dist[el1.ss][el1.ff] == 1e9) {
				dist[el1.ss][el1.ff] = dist[el.ss][el.ff] + 1;
				q.push_back(el1);
			}
		}
	}
	if (dist[n - 1][m - 1] == 1e9)  {
		cout << -1;
		return;
	}
	cout << all - dist[n - 1][m - 1] - 1;
}

void solve() {
	cin >> n >> m;
	gr.resize(n, vector<char> (m)); 
	dist.resize(n, vector<int> (m, 1e9));
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			cin >> gr[i][j];
			if (gr[i][j] == '.') {
				++all;
			}
		}
	}
	bfs();
}            

signed main() {
    /*!

    !*/
    cout.precision(10);
    cout << fixed;
    if (!debug) {
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
    }
 //   freopen("TASK.in", "r", stdin);
  // freopen("TASK.out", "w", stdout);
    solve();
    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <cmath>
using namespace std;

#define FOR(i,s,e) for (int i = int(s); i < int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()

int SURP = 1000000007;

int main(){
	long long int number[5] ={0};
	char c[] = {'M','A','R','C','H'};
	int N;

	cin >> N;
	FOR(i,0,N){
		string s;
		cin >> s;
		FOR(j,0,5){
			if (s[0] == c[j]) number[j]++;
		}
	}

	long long int ret = 0;

	for (int i = 0; i < 5; i++){
		for(int j = i+1;j < 5;j++){
			for(int k = j+1;k < 5;k++){
				ret += (number[i] *number[j] *number[k]);
			}
		}
	}


	cout << ret << endl;
	return 0;
}


Measured memory_bytes: 256
/* ~ Programmer >> Tushar Mahajan */
#include <iostream>
#include <bits/stdc++.h> 
using namespace std;
#define ll long long int
#define MOD 1000000007
#define ios ios_base::sync_with_stdio(false);cin.tie(NULL); 

int main() {
	ios;
	int n,rem,flag = false;
	cin>>n;
	while(n>0)
	{
	    rem = n%10;
	    if(rem == 7)
	    {
	        flag = true;
	        break;
	    }
	    n = n/10;
	}
	if(flag)
	{
	    cout<<"Yes";
	}
	else
	{
	    cout<<"No";
	}
	return 0;
}


Measured memory_bytes: 3692
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define po pop_back
#define fi first
#define se second
#define hello ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define MOD 998244353  
using namespace std;
bool comp(ll a,ll b){if(a>b)return true;else return false;}
int isP(ll n){if(n==1)return 0;if(n==2 || n==3)return 1;for(ll i=2;i<=sqrt(n);i++){if(n%i==0)return 0;}return 1;}
ll power(ll a,ll b){if(b==0)return 1;if(b==1) return a;ll t=power(a,b/2);if(b%2==1) return t*t*a;else return t*t;}
ll powMOD(ll x,ll y){if(y==0)return 1;if(y==1)return x;ll t=powMOD(x,y/2);if(y%2==1)return t*t%MOD*x%MOD;else return t*t%MOD;}
bool cmp(pair<ll,ll> p1,pair<ll,ll> p2){if(p1.fi>p2.fi) return true;if(p1.fi==p2.fi && p1.se>p2.se) return true;return false;}

int main()
{
    hello;
    
    ll t; 
//    cin>>t;
	t=1;
	
	while(t--){
		string s;
		cin>>s;
		if(s[s.size()-1]=='s'){
			s+="es";
		}
		else{
			s+="s";
		}
		cout<<s<<"\n";
	}
    
    return 0;  
}

Measured memory_bytes: 3672
#include<cstdio>
#include<cstring>
#include<cctype>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;
int read(){
    char c;int s=0,t=1;
    while(!isdigit(c=getchar()))if(c=='-')t=-1;
    do{s=s*10+c-'0';}while(isdigit(c=getchar()));
    return s*t;
}
int min(int a,int b){return a<b?a:b;}
int max(int a,int b){return a<b?b:a;}
int abs(int x){return x>0?x:-x;}
void mins(int &a,int b){if(a>b)a=b;}
void maxs(int &a,int b){if(a<b)a=b;}
//void insert(int u,int v){tot++;e[tot].v=v;e[tot].from=first[u];first[u]=tot;}
/*------------------------------------------------------------*/
const int inf=0x3f3f3f3f;

int n;
ll a[1010],ans,as;
int main(){
    n=read();
    ans=1;as=1;
    for(int i=1;i<=n;i++){
		a[i]=read();
		ans*=3;
		if(!(a[i]&1))as*=2;
	}
    printf("%lld",ans-as);
    return 0;
}

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

#define F first
#define S second
#define x1 privet1
#define x2 privet2
#define y1 privet3
#define y2 privet4
#define left privet6
#define prev ppppp

using namespace std;
typedef long long ll;

const int max_n = 50011, log_n = 32, max_m = 111, mod = 1000000007, inf = 1000111222;

ll a, b, c, d, n;

ll aa() {
    return min(min(min(a * 40, b * 20), c * 10), d * 5);
}

ll aaa(int n) {
    ll mn = 1000000000000000000LL;
    for (int i = 0; i <= n * 4; ++i) {
        for (int q = 0; q <= n * 2; ++q) {
            for (int w = 0; w <= n; ++w) {
                for (int e = 0; e <= n; ++e) {
                    if (i + q * 2 + w * 4 + e * 8 == n * 4) {
                        mn = min(mn, i * a + q * b + w * c + e * d);
                    }
                }
            }
        }
    }
    return mn;
}

int main() {
    //freopen("input.txt", "r", stdin);
    cin >> a >> b >> c >> d >> n;
    ll ans = 1LL * aa() * (n / 10);
    cout << ans + aaa(n % 10) << endl;
    return 0;
}


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

int main(){
  using v2 = vector<vector<int64_t>>;
  int N,W;
  cin >> N >> W;
  v2 vec;
  rep (i,0,N){
    int w,v;
    cin >> w >>v;
    vector<int64_t> vec1={w,v};
    vec.push_back(vec1);
  }
  v2  dp(N+1,vector<int64_t> (W+1,0));
  rep(i,1,N+1){
    rep(j,1,W+1){
      if (j-vec[i-1][0]<0){
        dp[i][j]=dp[i-1][j];
      }
      else{
        dp[i][j]=max(dp[i-1][j],dp[i-1][j-vec[i-1][0]]+vec[i-1][1]);
      }
    }
  }
  cout << dp[N][W] << endl;
}

Measured memory_bytes: 80256
#include <stdio.h>

int main(void)
{
	int N;
	scanf("%d",&N);
	int A[N+2],B[N+1],i;
	for(i = 1; i < N + 2; i++)
	{
		scanf("%d",&A[i]);
	}
	for(i = 1; i < N+1; i++)
	{
		scanf("%d",&B[i]);
	}
	int yoyuu = 0;
	long int maxkill = 0;
	for(i = 1; i < N+1; i++)
	{
		if(yoyuu >= A[i])
		{
			yoyuu = B[i];
			maxkill += A[i];
		}
		else if(yoyuu < A[i] && yoyuu >= 0)
		{
			maxkill+= yoyuu;
			A[i] -= yoyuu;
			if(B[i] >= A[i])
			{
				B[i] -= A[i];
				yoyuu = B[i];
				maxkill += A[i];
			}
			else{
				maxkill += B[i];
				yoyuu = 0;
			}
		}
	}
	if(yoyuu >= A[N+1])
	{
		maxkill += A[N+1];
	}
	else
	{
		maxkill+=yoyuu;
	}
	printf("%ld",maxkill);
	return 0;
}
			


Measured memory_bytes: 896
"""
a = int(input())
# スペース区切りの整数の入力
b, c = map(int, input().split())
# 文字列の入力
s = input()
# 出力
print(str(a+b+c) + " " + s)
"""


def main():
	while(1):

		N,n = map(int, input().split())
		
		if N == 0 and n == 0:
			break

		a = list(map(int, input().split()))
		ans = 0
		for i in range(N):
			for j in range(i+1,N):
				if a[i]+a[j] <= n and a[i]+a[j] > ans:
					ans = a[i]+a[j]

		if ans == 0:
			print("NONE")
		else:
			print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 5636
#include<iostream>
#include<algorithm>
#include<map>
#include<vector>

using namespace std;

typedef long long ll;

int N, M, X[100000];
int amari[100000];
int cnt[100001];
map<int, int> xc[100000];
int use[100000];

int main() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> X[i];
		cnt[X[i]]++;
		amari[X[i] % M]++;
	}

	for (int i = 0; i < N; i++) {
		xc[X[i] % M][X[i]]++;
	}
	for (int i = 0; i < 100000; i++)use[i] = -1;

	int ans = 0;
	
	for (int i = 0; i < M; i++) {
		if (use[i] == -1) {
		
			if((M % 2 == 0 && i == M / 2) || i == 0)use[i] = amari[i] / 2;
			else use[i] = min(amari[i], amari[M - i]);
			
			ans += use[i];
			use[M - i] = use[i];
			//cout << ans << " " << i << " " << amari[i] << " " << amari[M - i] << endl;
		}
	}
	for (int i = 1; i < M; i++) {
		if (M % 2 == 0 && i == M / 2)continue;
		vector<int> tmp;
		int binaryed = 0;
		for (auto it = xc[i].begin(); it != xc[i].end(); it++) {
			tmp.push_back((*it).second);
			if (tmp.back() % 2 == 1)binaryed++, tmp[tmp.size() - 1]--;
		}
		sort(tmp.begin(), tmp.end());
		
		int pointer = 0;
		use[i] -= binaryed;
		while (pointer < tmp.size() && use[i] > 0) {
			if (use[i] >= tmp[pointer]) {
				use[i] -= tmp[pointer];
				tmp[pointer] = 0;
			}
			else {
				tmp[pointer] -= use[i];
				use[i] = 0;
			}
			pointer++;
		}
		for (int j = 0; j < tmp.size(); j++) {
			ans += (tmp[j] / 2);
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 11440
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ll  long long
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define vi vector<int>
#define br cout <<"\n";
#define all(x)  (x).begin(),(x).end()
#define tr(c,i) for(auto i : c)
#define pii pair< int,int >
#define Fast_IO() ios_base::sync_with_stdio(false);cin.tie(nullptr)
#define pq priority_queue< pair<ll,pii> ,vector<pair<ll,pii>>,greater <pair<ll,pii>> >p;//container adapter makes ascending q
#define er(x) cout << x << " "
#define err(x,y) cout << x << " "<<y
using namespace std;
clock_t time_p = clock();
void dem()
{

        time_p=clock()-time_p;
        cerr<<"Time Taken : "<<(float)(time_p)/CLOCKS_PER_SEC<<"\n";
}
using namespace std ;
const ll MAX =  1000 * 1000 ;
const int dx[] = { 1, -1 , 0 , 0  };
const int dy [] = { 0 ,0 , 1 , -1  };
const int MOD = 1000 * 1000 * 1000 + 9 ;
const int N = 301 ;
const int INF = INT_MAX ;
const int M = 200005;
const double EPS = 1e-9 ;

int main (){
    int n ;
    cin >> n ;
    string s ;
    cin >> s ;
    bool ok = true ;
    if ( n &1) {cout << "No" ; return 0 ; }
    else {
    int j = n / 2 ;
    for (  int i = 0 ; 2 * i < n ; ++ i  ){
        if ( s[i] != s[ i + j ]){
            ok = false ;
        }
    }
    if ( ok )
        cout << "Yes" ;
        else
            cout << "No" ;
        br




    }

    return 0 ;
}




Measured memory_bytes: 256
lunlun=[]

def find_lunlun(n,curr):
    global lunlun
    if curr>n:
        return

    lunlun.append(curr)
    el= curr%10
    find_lunlun(n,curr * 10 + el)
    if el==9:
        find_lunlun(n,curr*10+el-1)
    elif el==0:
        find_lunlun(n,curr*10+el+1)
    else:
        find_lunlun(n,curr*10+el-1)
        find_lunlun(n,curr*10+el+1)

for i in range(1,10):
    find_lunlun(10**10,i)
lunlun.sort()

k=int(input())
print(lunlun[k-1])

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

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

    ll a[n][n], sum = 0;

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> a[i][j];
            if(i < j)   sum += a[i][j];
        }
    }

    for(int k = 0; k < n; k++){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(a[i][j] > a[i][k]+a[k][j]){
                    cout << "-1" << endl;
                    return 0;
                }
            }
        }
    }

    for(int i = 0; i < n; i++){
        for(int j = i+1; j < n; j++){
            bool need = true;
            for(int k = 0; k < n; k++){
                if(i == k || j == k)    continue;
                if(a[i][k]+a[k][j] == a[i][j])  need = false;
            }
            if(!need)   sum -= a[i][j];
        }
    }

    cout << sum << endl;

    return 0;
}

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

int main()
{
  int n, k;
  cin >> n >> k;
  int h[n];
  int dp[n];

  for (auto i = 0; i < n; i++) {
    cin >> h[i];
    dp[i] = numeric_limits<int>::max();
  }
  dp[0] = 0;
  for (auto i = 0; i < n; i++) {
    for (auto j = 1; j <= k; j++) {
      if (i + j < n) {
        dp[i + j] = min(dp[i + j], dp[i] + (h[i] < h[i + j] ? h[i + j] - h[i] : h[i] - h[i + j]));
      }
    }
  }
  cout << dp[n - 1] << endl;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i , n) for (int i = 0; i < (int)(n); i++)
const int INF = 1<<29;
using namespace std;
using ll = long long;
int main(){
    int n , m , a[111] , b , c , sum = 0;
	cin >> n;
	for(int i=1;i<=n;i++){
	    cin >> a[i];
        sum += a[i];
    }
	cin >> m;
	while(m--){
	    cin >> b >> c;
        cout << sum - a[b] + c << endl; 
    }
	return 0;
}


Measured memory_bytes: 3588