akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define int long long 

const int MAX_N = 400;
const int inf = 1LL << 60;

int dp[MAX_N][MAX_N];
int H[MAX_N],minH[MAX_N];

void chmin(int &a, int b){ if( a > b ){ swap(a,b);} return ;}

signed main(void){ 
  
  int N,K; cin >> N >> K; int m = N-K;
  
  for(int i = 0; i < N; i++){ cin >> H[i];}
  
  minH[0] = H[0];
  
  for(int i = 1; i < N; i++){ 
    minH[i] = min(H[i],minH[i-1]);
  }

  for(int i = 0; i < MAX_N; i++){
    for(int j = 0; j < MAX_N; j++){ 
      dp[i][j] = inf;
    }
  }
  
  dp[0][0] = 0; dp[0][1] = H[0];
  
  for(int i = 0; i < N; i++){ 
    for(int j = 0; j <= i+1; j++){ 
      
      for(int k = 0; k < i; k++){ 
        
        if( j >= 2 ){  // 最後にk番目をちゃんと選んだ場合
          chmin( dp[i][j], dp[k][j-1]+max(0LL, H[i]-H[k]) );
        }
        
        else if( j == 1 ){ //今まで何も選んでいない場合
          chmin( dp[i][j], H[i] );
        } //ここがおかしい　今までから一番小さなものを選ぶはず
          //やっぱりおかしくない
        
        else{ //今回も何も選ばない場合
          chmin( dp[i][0], 0 );
          
        }
      }
    }
  }
  
  int res = inf;
  
  for(int i = m-1; i < N; i++){
  chmin(res, dp[i][m]);
  }

  cout << res << endl;
  
  return 0;
} 
      

Measured memory_bytes: 2044
import copy
def BubbleSort(C, N) :
    for i in range(N-1) :
        for j in range(N-1, i, -1) :
            if C[j][1] < C[j-1][1] :
                C[j], C[j-1] = C[j-1], C[j]
    return(C)

def SelectionSort(C, N) :
    for i in range(N) :
        minj = i
        for j in range(i, N) :
            if C[j][1] < C[minj][1] :
                minj = j
        C[i], C[minj] = C[minj], C[i]
    return(C)

def Stable(A, B, N) :
    for i in range(N) :
        for j in range(i+1, N) :
            for a in range(N) :
                for b in range(a+1, N) :
                    if A[i][1] == A[j][1] and A[i] == B[b] and A[j] == B[a] :
                        return "false"
    return "true"

N = int(input())
OrgC = list(map(str, input().split()))
BubC = copy.copy(OrgC)
SelC = copy.copy(OrgC)
print(" ".join(BubbleSort(BubC, N)))
if Stable(OrgC, BubC, N) == "false" :
    print("Not stable")
else :
    print("Stable")

print(" ".join(SelectionSort(SelC, N)))
if Stable(OrgC, SelC, N) == "false" :
    print("Not stable")
else :
    print("Stable")




Measured memory_bytes: 6344
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#define REP(i, m, n) for(int i=int(m);i<int(n);i++)
#define EACH(i, c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s, e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())

//#define LOCAL 1
#ifdef LOCAL
#define DEBUG(s) cout << (s) << endl
#define dump(x)  cerr << #x << " = " << (x) << endl
#define BR cout << endl;
#else
#define DEBUG(s) do{}while(0)
#define dump(x) do{}while(0)
#define BR
#endif


//改造
typedef long long int ll;
using namespace std;


//ここから編集する


int main() {

    ll N;
    cin >> N;
//    REP(h,1,3501){
//        REP(j,1,3501){
//            if(Nhw % ())
//        }
//
//    }

    for(ll h = 1; h <= 3500; h++){
        for(ll w = 1; w <= 3500; w++){
            if( 4 * h * w - N * w - N * h > 0 && (N * h * w) % (4 * h * w - N * w - N * h) == 0 ){
                ll n = (N * h * w) / (4 * h * w - N * w - N * h);
                cout << h << " " << w << " " << n << endl;
                return 0;
            }
        }
    }

    return 0;
}


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

using namespace std;

int dp[1000001],dp2[1000001];

int main(void){

  vector<int>p;

  for(int i=1;i*(i+1)*(i+2)/6<1000001;i++){
    p.push_back(i*(i+1)*(i+2)/6);
  }

  fill(dp,dp+1000001,10000000);
  fill(dp2,dp2+1000001,10000000);
  dp[0]=dp2[0]=0;

  for(int i=0;i<1000001;i++){
    for(int j=0;j<p.size();j++){
      if(i-p[j]<0)break;
      dp[i]=min(dp[i],dp[i-p[j]]+1);
      if(p[j]%2==1)dp2[i]=min(dp2[i],dp2[i-p[j]]+1);
    }
  }

  int n;
  while(cin >> n,n){
    cout << dp[n] <<" "<<dp2[n]<< endl;
  }


  return 0;
}

Measured memory_bytes: 9032
import itertools

n,d = map(int,input().split())
x = [ list(map(int,input().split(" "))) for i in range(n)]
ns = [i for i in range(n)]
ans = 0
for v in itertools.combinations(ns, 2):
    k = 0
    for i in range(d):
        k += (x[v[0]][i] - x[v[1]][i]) ** 2
    if k ** 0.5 % 1 == 0:
        ans += 1
print(ans)


Measured memory_bytes: 3064
#include <iostream>
#include <cmath>
#include <math.h>
using namespace::std;

int mod(long long int m, long long int n, long long int b)
{
        long long int y,x,r;
        y=1;
        if(n>1)
        {
                if(n%2==0)
                {
                        x=(m*m)%b;
                        n=n/2;
                        r=mod(x,n,b);
                }
                else
                {
                        x=(m*m)%b;
                        y=y*(m%b);
                        n=(n-1)/2;
                        r=mod(x,n,b);

                }
        }
        else
        {
                r=m;
        }
        return (r*y)%b;

}
int main()
{
        long long int m,n,g;
        long long int b;
        b=1000000007;
        cin>>m>>n;
        g=mod(m,n,b);
        cout<<g<<endl;
}



Measured memory_bytes: 3112
#include "bits/stdc++.h"
using namespace std;
using ll = long long;

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

	string s;
	cin >> s;
	int ans = -1;
	int n = s.size();
	for (int i = 0, j = 0; i < n; i = j) {
		while(j < n && s[i] == s[j]) j++;
		ans++;
	}
	cout << ans;
}

Measured memory_bytes: 512
#include<iomanip>
#include<limits>
#include<thread>
#include<utility>
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<numeric>
#include<cassert>
#include<random>
#include<chrono>
#include<unordered_set>
#include<unordered_map>
#include<fstream>
#include<list>
#include<functional>
#include<bitset>
#include<complex>
#include<tuple>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef long double D;
typedef complex<D> P;
#define F first
#define S second
const ll E=1e18+7;
const ll MOD=1000000007;


template<typename T,typename U>istream & operator >> (istream &i,pair<T,U> &A){i>>A.F>>A.S; return i;}
template<typename T>istream & operator >> (istream &i,vector<T> &A){for(auto &I:A){i>>I;} return i;}
template<typename T,typename U>ostream & operator << (ostream &o,pair<T,U> &A){o<<A.F<<" "<<A.S; return o;}
template<typename T>ostream & operator << (ostream &o,vector<T> &A){ll i=A.size(); for(auto &I:A){o<<I<<(--i?" ":"");} return o;}
template<typename T>vector<T> & cset(vector<T> &A,T e=T()){for(auto &I:A){I=e;} return A;}



int main(){
    const ll MAX=1000000;
    vector<bool> P(MAX,true);
    for(ll i=2;i<MAX;i++){
        if(P[i]){
            for(ll j=2;i*j<MAX;j++){P[i*j]=false;}
        }
    }
    ll n,p;
    while(cin>>n>>p,n!=-1){
        vector<ll> A;
        for(ll i=max(2LL,n+1);A.size()<p+100;i++){
            if(P[i]){
                A.push_back(i);
            }
        }
        vector<ll> B;
        for(int i=0;i<A.size();i++){
            for(int j=i;j<A.size();j++){
                B.push_back(A[i]+A[j]);
            }
        }
        sort(B.begin(),B.end());
        cout<<B[p-1]<<endl;
    }
    
    
    
    return 0;
}



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

#define ll long long

const ll MOD = 1000000007;

int main() {
  int N;
  cin >> N;
  string S;
  cin >> S;
  
  
  vector<pair<int, ll>> domino;
  
  int i = 0;
  while (i < N) {
    if (S[i] == S[i+1]) {
      ll count = 0;
      while(S[i] == S[i+1]) {
        i += 2;
        count++;
      
        if (i >= N) break;
      }
      pair<int, ll> p = make_pair(1, count);
      domino.push_back(p);
    }
    if (S[i] != S[i+1]) {
     ll count = 0;
      while(S[i] != S[i+1]) {
        i++;
        count++;
      
        if (i >= N) break;

      }  
      pair<int, ll> p = make_pair(0, count);
      domino.push_back(p);
    }
    
  }
    
  
  ll ans = 0;
  
  if (domino[0].first == 0) {
    ans = 3;
    for (int i = 0; i < domino[0].second - 1; i++) {
      ans *= 2;
    }
    
  } else {
    ans = 6;
    for (int i = 0; i < domino[0].second - 1; i++) {
      ans *= 3;
    }
  }
  
  for (int i = 1; i < domino.size(); i++) {
    
    if (domino[i].first == 0) {
      for (int j = 0; j < domino[i].second -1; j++) {
        ans *= 2;
        ans %= MOD;
    } 
    } else {  
      ans *= 2;
      for (int j = 0; j < domino[i].second -1; j++) {
        ans *= 3;
        ans %= MOD;
      }
  
    }
  }
  cout << ans << endl;
  
  
}

Measured memory_bytes: 3616
#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
int main()
{
  while(1)
  {
    int n;
    cin>>n;
    if(n==0) break;
    int s[n];
    int sum=0;
    for(int i=0;i<n;i++)
    {
      cin>>s[i];
      sum+=s[i];
    }
    double dev=0;
    for(int i=0;i<n;i++)
    {
      dev+=pow(s[i]-sum*1.0/n,2);
    }
    cout<<fixed<<sqrt(dev/n)<<endl;
  }
}

Measured memory_bytes: 3244
#include <bits/stdc++.h>
#include <time.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll MOD = 1e9 + 7/*998244353*/;
const ll INF = 1LL << 60;
ll mod_pow(ll, ll, ll); ll mod_fact(ll, ll); ll mod_inv(ll, ll); ll gcd(ll, ll); ll lcm(ll, ll);
//
int main(){
    int n;
    cin >> n;
    if(n % 1000 == 0) cout << 0;
    else cout << (1000 - n % 1000);
}

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

signed main() {
  int n,m;
  cin >> n >> m;

  vector<int> a(n);
  int sum = 0;
  rep(i,n) {
    cin >> a[i];
    sum += a[i];
  }

  int cnt = 0;
  for (int i = 0; i < n; i++) {
    int vote = a[i];
    if(vote * 4 * m < sum);
    else cnt++;
  }

  if(cnt >= m) cout << "Yes" << endl;
  else cout << "No" << endl;

}



Measured memory_bytes: 3612
l = [list(map(int,input().split())) for i in range(3)]
n = int(input())
b = list(int(input()) for _ in range(n))
for i in range(3) :
    for j in range(3) :
        for k in range(n) :
            if l[i][j] == b[k] :
                l[i][j] = 0

for i in range(3) :
    if l[i][0] + l[i][1] + l[i][2] == 0 :
        print('Yes')
        exit()
    if l[0][i] + l[1][i] + l[2][i] == 0 :
        print('Yes')
        exit()
    if l[0][0] + l[1][1] + l[2][2] == 0 :
        print('Yes')
        exit()
    if  l[0][2] + l[1][1] + l[2][0] == 0 :
        print('Yes')
        exit()
print('No')

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

#define REP(i,n) for(long long i=0;i<n;++i)
#define REPR(i,n) for(long long i=n;i>=0;--i)
#define REPI(itr,v) for(auto itr=v.begin();itr!=v.end();++itr)
#define REPIR(itr,v) for(auto itr=v.rbegin();itr!=v.rend();++itr)
#define FOR(i,a,b) for(long long i=a;i<b;++i)
#define SORT(v,n) sort(v, v+n)
#define SORTV(v) sort(v.begin(), v.end())
#define ALL(v) v.begin(),v.end()
#define llong long long
#define INF 999999999
#define SUR 1000000007
#define pb push_back
#define pf push_front
#define MP make_pair
#define SV(v) {for(long long sitr=0;sitr<v.size();++sitr){cin>>v[sitr];}}

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

using namespace std;

typedef pair<int,int> pii;

bool windows[100*100][100] = {};

int main(){

  int n, h, w;
  scanf("%d %d %d", &n, &h, &w);
  REP(i,n){
    int x;
    scanf("%d", &x);
    for(int j = 0; j < w; ++j){
      for(int k = 0; k < h; ++k){
        if(i % 2 == 0){
          windows[i*w + j + x][k] = true;
        }else{
          windows[i*w + j - x][k] = true;
        }
      }
    }
  }

  llong ans = 0;
  REP(i,w*n){
    REP(j,h){
      if(!windows[i][j]){
        ans++;
      }
    }
  }

  printf("%lld\n", ans);
  return 0;
}




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

int main(){
  int N;
  cin >> N;
  vector<int> vec(N);
  for(int i=0; i<N; i++){
    cin >> vec.at(i);
  }
  sort(vec.begin(),vec.end());
  
  int gcd = vec.at(0);
  for(int i=1; i<N; i++){
   int a = vec.at(i);
   int b = gcd;
   int r = a % b;
    while(r!=0){
      a = b;
      b = r;
      r = a % b;
    }
    gcd = b;
  }
  
  cout << gcd << endl;
}

Measured memory_bytes: 640
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Threading.Tasks;

namespace AtCorder
{
	public class Program
	{
		static void Main(string[] args)
		{
			var nw = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
			int n = nw[0];
			int w = nw[1];

			var wv = new Tuple<long, long>[n];
			for (int i = 0; i < n; i++) {
				var temp = Console.ReadLine().Split(' ').Select(long.Parse).ToArray();
				wv[i] = new Tuple<long, long>(temp[0], temp[1]);
			}

			long max = wv.Sum(x => x.Item2);

			var dp = new long[n + 1, max + 1];
			for (int i = 0; i < n + 1; i++) {
				for (int j = 0; j < max + 1; j++) {
					dp[i, j] = long.MaxValue;
				}
			}

			dp[0, 0] = 0;

			for (int i = 1; i <= n; i++) {
				for (int j = 0; j < max + 1; j++) {
					if (dp[i - 1, j] == long.MaxValue) {
						continue;
					}

					long nextV = j + wv[i - 1].Item2;
					long nextW = dp[i - 1, j] + wv[i - 1].Item1;
					if (nextW <= w && nextV <= max) {
						dp[i, nextV] = Math.Min(dp[i, nextV], nextW);
					}

					dp[i, j] = Math.Min(dp[i, j], dp[i - 1, j]);
				}
			}

			long ans = 0;
			for (int i = 0; i < max + 1; i++) {
				if (dp[n, i] != long.MaxValue) {
					ans = Math.Max(ans, i);
				}
			}

			Console.WriteLine(ans);
		}
	}
}

Measured memory_bytes: 91360
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int N,Q;
vector<vector<int>> G(N);
vector<int> P(N);
vector<int> C(N);
vector<int> res(N);

void dfsP(int v,int p){
    P[v] = p;
    for(auto e: G[v]){
        if (e == 0 || P[e] != -1) continue;
        dfsP(e,v);
    }
}

void dfsQ(int p,int c){
    res[p] += c;
    for (auto e:G[p]){
        if (P[p] == e) continue;
        dfsQ(e,C[e] + c);
    }
};

int main() {
    cin >> N >> Q;
    G.assign(N,vector<int>());
    for (int i = 0;i < N - 1;i++){
        int a,b;cin >> a >> b;a--,b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    P.assign(N,-1);dfsP(0,-1);
    //for (int i = 0;i < N;i++) cout << P[i] << endl;
    res.assign(N,0);C.assign(N,0);
    for (int i = 0;i < Q;i++){
        int p,x;cin >> p >> x;p--;
        C[p] += x;
    }
    dfsQ(0,C[0]);
    for (int i = 0;i < N;i++) {
        if (i != N - 1) cout << res[i] << " ";
        else cout << res[i] << endl;
    }
}

Measured memory_bytes: 25088
#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>

using namespace std;

int main(){

	int hurui[200000]={0};
	int sosuu[100000];
	int cnt=0;
	vector<int> retu;
	int N,P;

	for(int i=2;i<=200000;i++){
		if(hurui[i]==0){
			sosuu[cnt]=i;
			cnt++;
			for(int j=i;j<=200000;j+=i){
				hurui[j]=1;
			}
		}
	}

	while(1){
		cin>>N>>P;
		if(N==-1&&P==-1) break;
		for(int i=0;;i++){
			if(sosuu[i]>N){
				for(int j=0;j<P;j++){
					for(int k=j;k<P+1;k++){
						retu.push_back(sosuu[i+j]+sosuu[i+k]);
					}
				}
				break;
			}
		}
		sort(retu.begin(),retu.end());
		cout<<retu[P-1]<<endl;
		retu.clear();
	}
}

Measured memory_bytes: 2136
#include <bits/stdc++.h> 
#define F(i,a,b) for(int i=a;i<=(b);++i)
#define dF(i,a,b) for(int i=a;i>=(b);--i)
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3f
#define pb push_back
#define maxnkp make_pair
#define fi first
#define se second
#define eps 1e-6
using namespace std;
typedef long long ll;
const int mods = 1e9+7;
const int maxn = 2e5+10;
const int N = 1e5+10;
const int E = 1e6+10; 
ll h;
ll pre[maxn];

void init(){
	ll cur = 1;
	pre[0]=cur;
	for(int i=1;i<=62;i++){
		cur*=2;
		pre[i] = pre[i-1]+cur;
	}
}

int main() {
	init();
	cin>>h;
	if(h==1){
		cout<<"1"<<endl;
		return 0;
	}
	if(h%2==1) h--;
	ll d = floor(log2(h));
	cout<<pre[d]<<endl;
}

Measured memory_bytes: 512
#include <cstdio>
#include <cctype>
#include <algorithm>
#define repu(i,x,y) for (int i=x; i<=y; ++i)
#define repd(i,x,y) for (int i=x; i>=y; --i)
using namespace std;

typedef long long LL;
const int p=1000000007;
int n,l[200100],r[200100],pow2[200100],f[200100],sum[200100];
struct data1
{
    int x,v,p;
    bool operator<(const data1 &t) const
    {
        return v<t.v;
    }
} a[200100];
struct data2
{
    int l,r;
    bool operator<(const data2 &t) const
    {
        return r<t.r || r==t.r && l>t.l;
    }
} b[200100];

int getint()
{
    char ch;
    while (!isdigit(ch=getchar()) && ch!='-');
    bool flag=ch=='-';
    if (flag)
        ch=getchar();
    int x=ch-'0';
    for (; isdigit(ch=getchar()); x=x*10+ch-'0');
    return flag?-x:x;
}

bool cmp(const data1 &a,const data1 &b)
{
    return a.x<b.x;
}

int main()
{
    n=getint();
    repu(i,1,n)
        a[i].x=getint(),a[i].v=getint();
    sort(a+1,a+1+n),pow2[0]=1;
    repu(i,1,n)
        a[i].p=i,pow2[i]=pow2[i-1]*2%p;
    sort(a+1,a+1+n,cmp),l[n+1]=n;
    repd(i,n,1)
        l[i]=min(l[i+1],a[i].p);
    repu(i,1,n)
        b[i]=(data2){l[i],r[i]=max(r[i-1],a[i].p)};
    sort(b+1,b+1+n),f[0]=sum[0]=1;
    for (int i=1,j=1,k; i<=n; ++i,j=k)
    {
        for (k=j; b[k].r==i; ++k)
            f[i]=(f[i]+LL(b[k].l>1?sum[i-1]+p-sum[b[k].l-2]:sum[i-1])*pow2[k-j])%p;
        sum[i]=(sum[i-1]+f[i])%p;
    }
    printf("%d\n",f[n]);
    return 0;
}

Measured memory_bytes: 8064
import math

n = int(input())

if n < 105:
    ans = 0
else:
    ans = 0
    for i in range(105,n+1,2):
        cnt = 0
        for j in range(1,int(math.sqrt(i))+1):
            if i % j == 0:
                #print(j)
                cnt += 2
        if cnt == 8:
            ans += 1
            #print(i)

print(ans)

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

int main() {
    int x,y,z,k;
    cin>>x>>y>>z>>k;
    vector<ll> a,b,c;
    ll p;
    for (int i=0; i<x; i++){
        cin>>p;
        a.push_back(p);
    }
    for (int i=0; i<y; i++){
        cin>>p;
        b.push_back(p);
    }
    for (int i=0; i<z; i++){
        cin>>p;
        c.push_back(p);
    }
    
    vector<ll> absum;
    
    for (int i=0; i<x; i++){
        for (int j=0; j<y; j++){
            ll q=a[i]+b[j];
            absum.push_back(q);
        }
    }
    sort(absum.begin(),absum.end());
    reverse(absum.begin(),absum.end());
    
    int q=min(x*y,k);
    
    vector<ll> ans;
    for (int i=0; i<q; i++){
        for (int j=0; j<z; j++){
            ll r=absum[i]+c[j];
            ans.push_back(r);
        }
    }
    sort(ans.begin(),ans.end());
    reverse(ans.begin(),ans.end());
    
    for (int i=0; i<k; i++) cout<<ans[i]<<endl;
}

Measured memory_bytes: 43256
#include <stdio.h>

int main(void) {
    int n, a, b, t;

    scanf("%d %d %d", &n, &a, &b);

    t = a*n;
    if (t > b) {
        printf("%d", b);
    } else if (t < b) {
        printf("%d", t);
    } else if (t == b) {
        printf("%d", t);
    }
return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,r,n) for(ll i = (ll)(r); i < (ll)(n); i++)
#define RFOR(i,r,n) for(ll i=(ll)(n-1);i>=r;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(x) x.begin(),x.end()
#define RALL(x) x.rbegin(),x.rend()
typedef long long int ll;
typedef vector<ll> vi;
typedef vector<pair<ll, ll> > vp;
typedef vector<string> vs;
typedef vector<char> vc;
typedef list<ll> lst;
typedef pair<ll, ll> P;
const long long INF = numeric_limits<ll>::max();
const long long MOD = 1000000007;
const long double PI = 3.1415926;
template <class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <class T> T &chmax(T &a, const T &b) { return a = max(a, b); }
 
ll n, m, k, ans = 0, sum = 0, cnt = 0;
string s;
//char c;
 
#define Endl endl
 
/*--------------------template--------------------*/
 
int main() {
    ll N;
    cin>>N;
    vector<vi> A(2, vi(N));
    REP(i,2)REP(j,N)cin>>A[i][j];
    ll a=A[0][0];
    ll b=a+A[1][0];
    FOR(i,1,N){
        a+=A[0][i];
        if(a>b)b=a+A[1][i];
        else b=b+A[1][i];
        //cout<<a<<","<<b<<endl;
    }
    cout<<b<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <string>
#include <map>
using namespace std;
int main()
{
 int i,t;
 long long int c;
 c=0;
 string s;
 map<string,long long int> m;
 cin >> t;
 while(t--)
 {
  cin >> s;
  sort(s.begin(),s.end());
  m[s]++;
 }
 for(auto it=m.begin();it!=m.end();it++)
 c+=(it->second*(it->second-1))/2;
 cout << c;
 return 0;
}

Measured memory_bytes: 11136
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
int main() {
  int k, n;
  cin >> k >> n;
  vector<int> a (n);
  vector<int> d (n);
  rep(i, n) cin >> a.at(i);
  
  d.at(0) = a.at(0) - a.at(n-1) + k;
  rep(i, n-1) d.at(i+1) = a.at(i+1) - a.at(i);
  sort (d.rbegin(), d.rend());
  
  cout << k - d.at(0) << endl;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  int h[100005] = {};
  int dp[100005] = {};

  cin >> n;

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

  dp[0] = 0;
  dp[1] = abs(h[0] - h[1]);
  for(int i=2; i<n; i++){
    dp[i] = min(abs(h[i] - h[i-1]) + dp[i-1] , abs(h[i] - h[i-2]) + dp[i-2]);
  }
  cout << dp[n-1] << endl;
  return 0;
}


Measured memory_bytes: 1024
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#include<cctype>
#include<set>
#include<queue>
#include<vector>
#include<map>
using namespace std;
typedef long long LL;

inline int read() {
	int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
	for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}

const int N = 500005;
struct Edge{
	int fr, to, nxt; 
}e[N << 1];
int head[N], f1[N], f2[N], c1[N], c2[N], sk[N << 1], ans[N], top = 0, En = 1;
bool vis[N << 1];

inline void add_edge(int u,int v) {
//	cout << u << " " << v << "\n";
	++En; e[En].fr = u, e[En].to = v, e[En].nxt = head[u]; head[u] = En;
	++En; e[En].fr = v, e[En].to = u, e[En].nxt = head[v]; head[v] = En;
}
void dfs(int u) {
	while (1) {
		int k = head[u]; 
		if (!k) break;
		head[u] = e[k].nxt;
		if (!vis[k]) {
			vis[k] = vis[k ^ 1] = 1;
			dfs(e[k].to);
			sk[++top] = k;
		}
	}
}
int main() {
//	freopen("1.txt", "r", stdin);
	int n = read();
	for (int i = 1; i <= n; ++i) {
		int x = read();
		if (x == -1) x = 0;
		f1[i] = x, c1[x] ++;
		add_edge(x, i);
	}
	for (int i = 1; i <= n; ++i) {
		int x = read();
		if (x == -1) x = 0;
		f2[i] = x, c2[x] ++;
		if (x == 0) add_edge(x, i + n);
		else add_edge(x + n, i + n);
	}
	for (int i = 1; i <= n; ++i) {
		ans[i] = -1;
		if (c1[i] % 2 != c2[i] % 2) { puts("IMPOSSIBLE"); return 0; }
		if ((c1[i] & 1) && (c2[i] & 1)) ans[i] = 0;
		else add_edge(i, i + n);
	}
	puts("POSSIBLE");
	dfs(0);
	for (int i = top; i >= 1; --i) {
		int k = sk[i];
		if (e[k].fr >= 1 && e[k].fr <= n && e[k].to >= n + 1 && e[k].to <= n + n) ans[e[k].fr] = 1;
//		if (e[k].fr >= n + 1 && e[k].fr <= n + n && e[k].to >= 1 && e[k].to <= n) ans[e[k].fr] = -1;
	}
	for (int i = 1; i <= n; ++i) {
		printf("%d ", ans[i]);
	}
	return 0;
}

Measured memory_bytes: 33408
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned ll
#define PI acos(-1)
#define vi vector<int>
#define pi pair<int, int>
#define pl pair<ll, ll>
template<typename T> using v2 = vector<vector<T>>;
template<typename T> using v3 = vector<vector<vector<T>>>;
template<class T> istream &operator>>(istream&is,vector<T>&v){for(auto &elemnt:v)is>>elemnt;return is;}
template<class T,class U> istream &operator>>(istream&is,pair<T,U>&p){is>>p.first>>p.second;return is;}
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; }
const int MOD = 1e9 + 7;
const int INF = 1e9 + 200;
const ll INFLL = 2e18 + 200;

int main() {
    int N;
    cin >> N;
    vector<ll> A(N);
    cin >> A;
    sort(A.begin(), A.end());
    __int128_t ans = 1;
    for (int i = 0; i < N; i++) {
        ans *= A[i];
        if (ans > (__int128_t) 1e18) {
            cout << -1 << endl;
            return 0;
        }
    }
    cout << (ll) ans << endl;
}


Measured memory_bytes: 4064
#include<bits/stdc++.h>
#define ll long long int
#define mod 1000000007
#define MAX 10000003
#define pb push_back
// #define mp make_pair
#define mem(x,y) memset(x,y,sizeof(x))
#define lcm(a,b) (a*b)/__gcd(a,b)
#define set_bit_count(x) __builtin_popcount(x)
#define str_rev(str) reverse(str.begin(),str.end())
#define loop(i,x,y) for(ll i=x;i<y;i++)
#define rloop(i,x,y) for(ll i=x-1;i>=y;i--)
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
int main()
{
    fastio;
    float n;
    cin>>n;
    float ans=n*44;
    cout << ans/7 << endl;
    return 0;
}

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

signed
main(){
	int N,M,P;
	while(cin >> N >> M >> P){
		if(N==0) break;
		vector<int> x(N);
		int sum = 0;
		for(int i=0;i<N;i++)
		{
			cin >> x[i];
			sum += x[i];
		}
		sum *= 100;
		double ret = sum * (100-P)/ (double)100;
		cout << ( (x[M-1]==0) ? 0 : (int)(ret/x[M-1]) ) << endl;
	}
}


Measured memory_bytes: 3084
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
#include<stack>
#include<queue>
#include<deque>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
#define FOR(i,n) for(int (i)=0;(i)<(n);(i)++)
#define FOR1(i,n) for(int (i)=1;(i)<(n);(i)++)
#define eFOR(i,n) for(int (i)=0;(i)<=(n);(i)++)
#define eFOR1(i,n) for(int (i)=1;(i)<=(n);(i)++)
#define SORT(i) sort((i).begin(),(i).end())
#define rSORT(i) sort((i).begin(),(i).end(), greater<int>());
#define YES(i) cout << ((i) ? "Yes" : "No") << endl;
constexpr auto INF = 1000000000;
constexpr auto LLINF = 922337203685477580;//7;
constexpr auto mod = 1000000007;

int main() {

	int n;
	cin >> n;
	int u, v, w;
	vector<vector<pair<int, int>>> g(n);
	FOR(i, n - 1) {
		cin >> u >> v >> w;
		u--; v--; w %= 2;
		g[u].push_back({ v,w });
		g[v].push_back({ u,w });
	}
	VI ans(n);
	queue<pair<int,int>> bfs;
	bfs.push({ 0,1 });
	pair<int, int> a;
	vector<bool> vis(n, 0);
	while (!bfs.empty()) {
		a = bfs.front();
		bfs.pop();
		ans[a.first] = a.second;
		vis[a.first] = 1;
		for (auto b : g[a.first]) {
			if (vis[b.first])continue;
			if (b.second % 2)bfs.push({ b.first,1 - a.second });
			else bfs.push({ b.first,a.second });
		}
	}
	for (auto e : ans)cout << e << endl;
}

Measured memory_bytes: 6912
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
#include <numeric>
#include <string>
#include <cmath>
#include <iomanip>
#include <queue>
#include <list>
#include <set>
#include <stack>
#include <cctype>
#include <cmath>
#include <bitset>

using namespace std;

/* typedef */
typedef long long ll;

/* constant */
const int INF = 1 << 30;
const int NIL = -1;
const int MAX = 10000;
const int mod = 1000000007;
const double pi = 3.141592653589;

/* global variables */

/* function */

/* main */
int main(){

    int n, m, x;
    cin >> n >> m;
    bitset<28> mask(0);
    for (int i = 0; i < m; i++) {
        cin >> x;
        mask.set(x);
    }
    // Print bit if binary(i) includes only mask bits

    /*
    // 1 ============================
    for (int i = 0; i < (1 << n); i++) {
        bitset<28> bs(i);
        if ((bs | mask) == mask) {
            printf("%d:", i);
            for (int j = 0; j < n; j++) {
                if ((bs >> j)[0]) printf(" %d", j);
            } 
            printf("\n");
        }
    }
    */

    // 2 ===========================
    int mask_int = mask.to_ulong();
    for (int b = 0; b < (1 << n); b++) {
        if ((b | mask_int) == mask_int) {
            printf("%d:", b);
            for (int i = 0; i < n;i++)
                if( (b >> i) & 1)
                    printf(" %d", i);
            printf("\n");
        }
    }

}



Measured memory_bytes: 3212
#include <iostream>
#include <algorithm>
#include <complex>
#include <vector>
#include <deque>
#include <queue>
#include <list>
#include <stack>
#include <string>
#include <functional>
#include <numeric>
#include <cmath>
#include <iomanip>
#include <map>
#include <set>
#include <cstdlib>

#define rep(i, b) for(int i = 0; i < b; i++)
#define repi(i, a, b) for(int i = a; i < b; i++)
#define all(c) c.begin(),c.end()
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define MAX_V 1001
#define MAX_E 401
#define INF INT_MAX
#define MOD 1000000007
#define EPS 1e-7
typedef long long ll;
inline int toInt(std::string s) { int v; std::istringstream sin(s); sin >> v; return v; }
template<class T> inline std::string toString(T x) { std::ostringstream sout; sout << x; return sout.str(); }
using namespace std;

typedef double D;      // 座標値の型。doubleかlong doubleを想定
typedef complex<D> P;  // Point
typedef pair<P, P> L;  // Line
#define X real()
#define Y imag()
typedef pair<int, int> pii;

int main()
{
	ll N;
	ll ans = 0;
	cin >> N;
	vector<string> S(N);
	rep(i, N)
	{
		cin >> S[i];
	}

	ll MARCH[5] = { 0, 0, 0, 0, 0 };
	rep(i, N)
	{
		if (S[i][0] == 'M')
		{
			MARCH[0]++;
		}
		if (S[i][0] == 'A')
		{
			MARCH[1]++;
		}
		if (S[i][0] == 'R')
		{
			MARCH[2]++;
		}
		if (S[i][0] == 'C')
		{
			MARCH[3]++;
		}
		if (S[i][0] == 'H')
		{
			MARCH[4]++;
		}
	}

	rep(i, 5)
	{
		repi(j, i + 1, 5)
		{
			repi(k, j + 1, 5)
			{
				ans += MARCH[i] * MARCH[j] * MARCH[k];
			}
		}
	}

	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 6144
#include <stdio.h>

int abs(int a){
	if(a>0) return a;
	else return -a;
}

int min(int a, int b){
	if(a>b) return b;
	else return a;
}

int main(void){
	int N;
	int h[100000];
	int i;

	scanf("%d", &N);
	for(i=0; i<N; i++) scanf("%d",&h[i]);

	int c[100000];
	c[0]=0;
	c[1]=abs(h[0]-h[1]);
	for(i=1; i+1<N; i++)
		c[i+1] = min( c[i-1]+abs(h[i-1]-h[i+1]) , c[i]+abs(h[i]-h[i+1]) );
	printf("%d\n",c[N-1] );
}




Measured memory_bytes: 896
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func nextInt(sc *bufio.Scanner) int {
	sc.Scan()
	t, _ := strconv.Atoi(sc.Text())
	return t
}

func swap(a []int, b, e, t int) {
	for k := 0; k < e-b; k++ {
		a[b+k], a[t+k] = a[t+k], a[b+k]
	}
}

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	n := nextInt(sc)
	a := make([]int, n)
	for i := range a {
		a[i] = nextInt(sc)
	}
	q := nextInt(sc)
	for i := 0; i < q; i++ {
		b := nextInt(sc)
		e := nextInt(sc)
		t := nextInt(sc)
		swap(a, b, e, t)
	}
	wtr := bufio.NewWriter(os.Stdout)
	for i := 0; i < n; i++ {
		if i > 0 {
			fmt.Fprint(wtr, " ")
		}
		fmt.Fprint(wtr, a[i])
	}
	fmt.Fprintln(wtr)
	wtr.Flush()
}



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

bool isPrime(int x){
  if(x<=1)return false;
  for(int i=2;i*i<=x;i++){
    if(x%i==0)return false;
  }
  return true;
}

int main(){
  int N=1<<15;
  vector<int> p;
  rep(i,N+1){
    if(isPrime(i))p.push_back(i);
  }

  vector<int> ans(N+1,0);
  rep(i,p.size())rep(j,i+1){
    if(p[i]+p[j] <= N) ans[p[i]+p[j]]++;
  }

  int n;
  while(cin >> n, n){
    cout << ans[n] << endl;
  }
}

Measured memory_bytes: 1272
#include<bits/stdc++.h>
using namespace std;
#define gc getchar_unlocked
#define fo(i,n) for(i=0;i<n;i++)
#define Fo(i,k,n) for(i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
#define ll long long
#define ull unsigned long long
#define si(x)	scanf("%d",&x)
#define sl(x)	scanf("%lld",&x)
#define ss(s)	scanf("%s",s)
#define pi(x)	printf("%d\n",x)
#define pl(x)	printf("%lld\n",x)
#define ps(s)	printf("%s\n",s)
#define deb(x) cout << #x << "=" << x << endl
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define meme(x) memset(x, 0, sizeof(x))
#define sortall(x) sort(all(x))
#define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
#define PI 3.1415926535897932384626
#define mod 1'000'000'007
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pl;
typedef vector<int>		vi;
typedef vector<ll>		vl;
typedef vector<pii>		vpii;
typedef vector<pl>		vpl;
typedef vector<vi>		vvi;
typedef vector<vl>		vvl;
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
	uniform_int_distribution<int> uid(0,lim-1);
	return uid(rang);
}

int main() {
    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
#endif
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    srand(chrono::high_resolution_clock::now().time_since_epoch().count());
    int h,w,i,j;
    cin>>h>>w;
    char arr[h][w];
    fo(i,h){
        fo(j,w){
            cin>>arr[i][j];
        } 
    } 
    ll dp[h][w];
    dp[0][0]=1;
    Fo(i,1,h){
        if(arr[i][0]=='#'){
            dp[i][0] = 0;
        }else{
            dp[i][0] = dp[i-1][0];
        }
    }
    Fo(i,1,w){
        if(arr[0][i]=='#'){
            dp[0][i] = 0;
        }else{
            dp[0][i] = dp[0][i-1];
        }
    }
    Fo(i,1,h){
        Fo(j,1,w){
            if(arr[i][j]=='#'){
                dp[i][j]=0;
            }else{
                dp[i][j]=(dp[i-1][j]+dp[i][j-1])%mod;
            }
        }
    }
    cout<<(dp[h-1][w-1])%mod<<"\n";
}


Measured memory_bytes: 12328
<?php
  list($k) = explode(" ", trim(fgets(STDIN)));

  if($k % 2 == 0){
    echo intdiv($k,2)*intdiv($k,2);
  }else{
    echo intdiv($k,2)*(intdiv($k,2)+1);
  }
  echo PHP_EOL;

Measured memory_bytes: 16060
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

int main(){
	
	string str[2000];
	
	int n;
	
	n = 10;
	
	for(int i = 0; i < 1000; i++){
		cin >> str[i];
		if(cin.eof()){
			n = i + 1;
			break;
		}
	}
	
	int max_size, max_num, sum, ans_size, ans_num;
	
	max_size = 0;
	max_num = 0;
	
	for(int i = 0; i < n; i++){
		if(str[i].size() > max_size){
			ans_size = i;
			max_size = str[i].size();
		}
		
		sum = 0;
		
		for(int j = 0; j < n; j++){
			if(str[i] == str[j]){
				sum++;
			}
		}
		
		if(sum > max_num){
			max_num = sum;
			ans_num = i;
		}
	}
	
	cout << str[ans_num] << " " << str[ans_size] << endl;
	
	return 0;
}

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

struct Data{
  
  string L;
  int P,A,B,C,D,E,F,S,M;
  int t;
  int income;
  double eff;

  bool operator<(const Data& data)const{
    if(eff != data.eff)return eff > data.eff; 
    return L < data.L;
  }
  
};
int main(){
  
  int N;
  Data list[50];
  
  while(1){
    
    cin >>N;
    if(N==0)break;

    for(int i=0 ; i < N ; i++){
      cin >>list[i].L>>list[i].P>>list[i].A>>list[i].B>>list[i].C>>list[i].D>>list[i].E>>list[i].F>>list[i].S>>list[i].M;
      list[i].t=list[i].A+list[i].B+list[i].C+(list[i].D+list[i].E)*list[i].M;
      list[i].income=(list[i].F*list[i].M*list[i].S)-list[i].P;
      list[i].eff=(double)list[i].income/list[i].t;
    }
    
    sort(list,list+N);
    
    for(int i=0 ; i < N ; i++){
      cout <<list[i].L<<endl;
    }
    cout <<"#"<<endl;
    
  }
  
  return 0;
}

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

int main() {
  ll ans,a=0,count=0,las=0;
  string s;
  cin >> s;
  r(i,s.size()){
    if(s[i]=='B'){
      a+=i; count++;
    }
  }
  cout<<(s.size()*2-count-1)*count/2-a<<endl;
}

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

int main() {
  int h, w;
  cin >> h >> w;

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

  for (int i = 0; i < h; i++) {
      cout << "#";
      string s;
      cin >> s;
      cout << s;
      cout << "#" << endl;
  }

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


Measured memory_bytes: 3628
package main

import (
	"fmt"
)

func main(){
	var a, b, c int
	fmt.Scan(&a, &b, &c)

	if a <= b && b <= c {
		fmt.Printf("%d %d %d\n", a, b, c)
	}else if b <= a && a <= c {
		fmt.Printf("%d %d %d\n", b, a, c)
	}else if b <= c && c <= a {
		fmt.Printf("%d %d %d\n", b, c, a)
	}else if c <= a && a <= b {
		fmt.Printf("%d %d %d\n", c, a, b)
	}else {
		fmt.Printf("%d %d %d\n", c, b, a)
	}
}


Measured memory_bytes: 1120
#include <bits/stdc++.h>
#define FASTIO ios::sync_with_stdio(false);cin.tie(0);
#define ADD +
#define SUBTRACT -
#define MULTIPLY *
#define DIVIDE /
#define MOD %
#define INCREMENT(x) ++x
#define DECREMENT(x) --x
#define in(a,b) cin>>a>>b;
#define out(a,b) cout<<a<<endl<<b<<endl;
#define scan(a) scanf("%d",&a);
#define print(a) printf("%d\n",a);
#define scanii(a,b) scanf("%d %d",&a,&b);
#define printii(a,b) printf("%d\n%d\n",a,b);
#define scaniii(a,b,c) scanf("%d %d %d",&a,&b,&c);
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define ll long long
#define ull unsigned long long
#define sll signed long long
#define f1(i,a) for(int i=0;i<a;++i)
#define f2(i,a) for(int i=a-1;i>=0;--i)
#define pi acos(-1)
#define mod 1000000007
#define TRUE 1
#define FALSE 0
#define ZERO 0
#define MP make_pair
#define F first
#define S second
#define en puts("");
#define elif else if
typedef ll int lli;
typedef sll int slli;
typedef ull int ulli;
const int sz=10000;
using namespace std;

int clue();
int result();
void show();
bool check();

int main() {

    int l,r,d;
    cin>>l>>r>>d;
    int c=0;
    for(int i=l;i<=r;++i) {
        if(i%d==0)++c;
    }
    cout<<c<<endl;
    
    return 0;
}

Measured memory_bytes: 3608
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<vector>
#include<string.h>
#include<math.h>
#include<map>
#include<iomanip>
#include<queue>

using ll = long long;
using ull = unsigned long long;

using namespace std;

const int inf = 1e6 + 7;

int main(){	
	
	int h , w;
	cin >> h >> w;
  char c[h][w];
  for(int i = 0; i < h; i++){
  	for(int j = 0; j < w; j++){
  		cin >> c[i][j];
  	}
  }
  
  for(int i = 1; i < h; i++){
  	for(int j = 1; j < w; j++){
	  	if(c[i][j] == '#'){
	  		if(c[i - 1][j] == '#' && c[i][j - 1] == '#'){
	  			cout << "Impossible" << endl;
	  			return 0;
	  		}
	  	}
  	}
  }
  
   for(int i = 0; i < h - 1; i++){
  	for(int j = 0; j < w - 1; j++){
	  	if(c[i][j] == '#'){
	  		if(c[i + 1][j] == '#' && c[i][j + 1] == '#'){
	  			cout << "Impossible" << endl;
	  			return 0;
	  		}
	  	}
	  }
  }
  
  cout << "Possible" << endl;
	return 0;
}
 

Measured memory_bytes: 3608
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define hi(x)((x)>>16)
#define lo(x)((x)&0xffff)
#define Z(a,b)v.push_back((a<<16)+b)

struct comp{bool operator()(const unsigned a,const unsigned b){return hi(a)*lo(a)<hi(b)*lo(b);}};
int main(){
	int n,w,d;
	for(;scanf("%d%d%d",&n,&w,&d),w;puts("")){
		vector<unsigned>v;
		Z(w,d);
		for(;n--;){
			int p,s,state=0;
			scanf("%d%d",&p,&s);p--;
			s%=hi(v[p])+lo(v[p]);
			unsigned x=hi(v[p]),y=lo(v[p]),_x=0,_y=0,x1,x2,y1,y2;
			for(;s--;)if(state==0){_x++;if(_x==x)state=1;}else _y++;
			if(state==0)x1=_x,x2=x-_x,y1=y2=y;
			else x1=x2=x,y1=_y,y2=y-_y;

			v.erase(v.begin()+p);
			if(x1*y1>x2*y2)
				Z(x2,y2),Z(x1,y1);
			else
				Z(x1,y1),Z(x2,y2);
		}

		for(sort(v.begin(),v.end(),comp());v.size();){
			printf("%d",hi(v[0])*lo(v[0]));
			v.erase(v.begin());
			if(v.size())printf(" ");
		}
	}
}

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

int main(){
  int n;
  cin >> n;
  
  vector <int> l(n);
  for (int i = 0; i < n; i++){
    cin >> l.at(i);
  }
  sort(l.rbegin(), l.rend());
  
  int ans = 0;
  for (int i = 0; i < n - 2; i++){
    for (int j = i + 1; j < n - 1; j++){
      if (l.at(i) >= l.at(j) + l.at(j + 1)) break;
      int L = j + 1, R = n;
      while (L + 1 < R){
        int c = (L + R) / 2;
        if (l.at(i) < l.at(j) + l.at(c)){
          L = c;
        }else{
          R = c;
        }
      }
      ans += L - j;
    }
  }
  
  cout << ans << endl;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define USE_LLONG_AS_INT
#ifdef USE_LLONG_AS_INT
#define int long long
#define inf (1ll<<60)
#else
#define inf (1<<30)
#endif
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back
#define pi pair<int,int>
#define vp vector<pair<int,int>>
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define MEMSET(a) memset(a,0,sizeof(a))
#define Yes(f) cout<<(f?"Yes":"No")<<endl
#define yes(f) cout<<(f?"yes":"no")<<endl
#define YES(f) cout<<(f?"YES":"NO")<<endl
#define SORT(v) sort(all(v))
#define RSORT(v) sort(all(v), greater<int>())

using namespace std;

const int mod=1e9+7;
const string sp=" ";

void run();

void init() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout<<fixed<<setprecision(12);
}

signed main(){
    init();
    run();
    return 0;
}

void run(){
    int n;
    cin>>n;
    vp a;
    REP(i,1,n){
        REP(j,i+1,n){
            if(n%2&&i+j==n)continue;
            if(n%2==0&&i+j==n+1)continue;
            a.pb({i,j});
        }
    }
    cout<<a.size()<<endl;
    for(pi b:a){
        cout<<b.fi<<sp<<b.se<<endl;
    }
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
#define int long long
#define P pair<int,int>
#define PP pair<P,int>
#define F first
#define S second
#define f(i,n) for(int i=0;i<(n);i++)
#define INF LLONG_MAX/3
#define eps LDBL_EPSILON
#define mod (int)(1000000007)
#define pie 3.141592653589793238462643383279
#define Bpri priority_queue
#define Spri priority_queue<P,vector<P>,greater<P>>
using namespace std;
signed main(){
	int a,b,c,d;
	cin>>a>>b>>c>>d;
	cout<<a/2.0*b<<" ";
	if(a/2==c&&b/2==d&&a%2==0&&b%2==0)cout<<1;
	else cout<<0;
	puts("");
}


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

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

    int l[n];
    for (int i = 0; i < n; i++){
        cin >> l[i];
    }

    int d = 0;
    int count = 1;

    for(int i = 0; i < n; i++){
        d = d + l[i];
        if(d <= x) count++;
    }

    cout << count << "\n";
    return 0;
}

Measured memory_bytes: 256
# coding: utf-8

import math

n, x = map(int, input().split())
minimum = 1000
total = 0
for i in range(n):
    dounats = int(input())
    total += dounats
    if dounats <= minimum:
        minimum = dounats
now = x - total
a = math.floor(now / minimum)
print(n + a)

Measured memory_bytes: 9096
# coding: utf-8
# Here your code !

n = input()

A = []
for i in range(n):
    A.append(raw_input().split())
    
s = []
h = []
c = []
d = []  # mark???????????????
for i in range(n):
    if A[i][0] == 'S' :
        s.append(int(A[i][1]))
    elif A[i][0] == 'H':
        h.append(int(A[i][1]))
    elif A[i][0] == 'C':
        c.append(int(A[i][1]))
    elif A[i][0] == 'D':
        d.append(int(A[i][1]))

for i in range(1,14): #1-13?????§?????????
    judge = True
    for j in range(len(s)): 
        if i == s[j] :
            judge = False
            break
    if judge :    
        print "S",i
for i in range(1,14): #1-13?????§?????????
    judge = True
    for j in range(len(h)): 
        if i == h[j] :
            judge = False
            break
    if judge :    
        print "H",i
for i in range(1,14): #1-13?????§?????????
    judge = True
    for j in range(len(c)): 
        if i == c[j] :
            judge = False
            break
    if judge :    
        print "C",i
for i in range(1,14): #1-13?????§?????????
    judge = True
    for j in range(len(d)): 
        if i == d[j] :
            judge = False
            break
    if judge :    
        print "D",i

Measured memory_bytes: 6484
import java.util.Scanner;
import java.math.BigInteger;

class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
for(int i=0;i<n;i++){
BigInteger a=sc.nextBigInteger();
BigInteger b=sc.nextBigInteger();
a=a.add(b);
if(a.toString().length()>80){
System.out.println("overflow");
}
else{
System.out.println(a);
}
}
}
}

Measured memory_bytes: 18588
#include<iostream>
#include<stdio.h>
using namespace std;

int main() {
	int num;
	int sum;
	int sell;
	int pluss;
	int tanka;
	int suryo;
	
	num = 0;
	sell = 0;
	sum = 0;
	while ( ~scanf("%d,%d", &tanka,&suryo) ) {
		num++;
		sell += suryo;
		sum += tanka * suryo;
	}
	
	if ( (sell % num) * 10 >= 5 )
		pluss = 1;
	else 
		pluss = 0;
	cout << sum << endl << sell / num + pluss << endl;
}

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

int main(void){
    string s;
    cin >> s;
    if(s[0] == s[s.length()-1]){
        if(s.length()%2 == 0){
            cout << "First" << endl;
        }else{
            cout << "Second" << endl;
        }
    }else{
        if(s.length()%2 == 0){
            cout << "Second" << endl;
        }else{
            cout << "First" << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 512
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		StringBuilder out = new StringBuilder();
		while (true) {
			int n = sc.nextInt();
			int s = sc.nextInt();
			if (n == 0 && s == 0)
				break; 
			// ways[k][x] := (counts of ways to reach x by sum of k nums)
			int ways[][] = new int[11][101]; // sufficient
			for (int bit = 0; bit < (1 << 10); ++bit) {
				int cnt1 = 0; // counts of 1 of bit.
				int sum = 0;
				for (int j = 0; j < 10; ++j)
					if (((bit >> j) & 1) == 1) { // lowest bit of (bit >> j) is 1?
						sum += j;
						++cnt1;
					}
				ways[cnt1][sum] += 1;
			}
			out.append(ways[n][s] + "\n");
		}
		System.out.print(out);
	}
}


Measured memory_bytes: 26804
N = int(input())

A = list(map(int, input().split()))

cnt = [0 for i in range(100001)]

for x in A:
    cnt[x] += 1

oddOrEven = 0

types = 0

for x in cnt:
    if(x > 0):
        types += 1
        oddOrEven += x

if((oddOrEven - types) % 2 == 0):
    print(types)
else:
    print(types - 1)


Measured memory_bytes: 14008