akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <iomanip>
#include <bitset>
#include <set>
#include <map>
#include <stdio.h>
#include <numeric>
#include <cstring>

#define rep(i,n) for (int i = 0; i < (n); i++)
#define rep1(i,n) for (int i = 1; i < (n); i++)
#define FOR(i,a,b) for (int i=(a); i < (b); i++)
#define MOD 1000000007 //10^9+7
using namespace std;
using ll = long long;
using PII = pair<int, int>;
const int INF = numeric_limits<int>::max();

// 負の数にも対応した % 演算
long long mod(long long val, long long m) {
    long long res = val % m;
    if (res < 0) res += m;
    return res;
}

//greatest common divisor
long long gcd(ll a, ll b) 
{
    if (a % b == 0) {
        return b;
    } else {
        return gcd(b, a % b);
    }
}

//least common multiple
long long lcm(ll a, ll b)
{
    return a / gcd(a, b) * b ;
}

int main()
{
    int x, y; cin >> x >> y;
    if (y % 2 == 1) {
        cout << "No" << endl;
        return 0;
    }

    if (y >= x * 2 && y <= x * 4) {
        cout << "Yes" << endl;
        return 0;
    }
    cout << "No" << endl;
    return 0;
}


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

using namespace std;

int main(){
  
  int a, b, n, y, x;

  while(cin >> a >> b >> n){

    if(!a && !b) break;

    int field[b][a];
    int mfield[b + 2][a + 2];
    bool check[b][a];
    
    // Empty
    for(int i = 0; i < b + 2; ++i){
      for(int j = 0; j < a + 2; ++j){
	if(i >= 0 && i < b && j >= 0 && j < a){
	  field[i][j] = 0;
	  check[i][j] = false;
	}
	mfield[i][j] = 0;
      }
    }

    // Start
    field[0][0] = 1;
    mfield[1][1] = 1;
    
    // Construction
    for(int i = 0; i < n; ++i){
      cin >> x >> y;
      field[y - 1][x - 1] = 2;
      mfield[y + 1][x + 1] = 0;
    }
    
    // Goal
    field[b - 1][a - 1] = 3;
    
    mfield[0][1] = 1;
    for(int i = 1; i <= b; ++i){
      for(int j = 1; j <= a; ++j){
	if(!check[i - 1][j - 1] && field[i - 1][j - 1] != 2){
	  mfield[i][j] = mfield[i - 1][j] + mfield[i][j - 1];
	  check[i - 1][j - 1] = true;
	}
	/*
	for(int k = 0; k < b + 2; ++k){
	  for(int l = 0; l < a + 2; ++l){
	    cout << mfield[k][l];
	  }
	  cout << endl;
	}
	cout << endl;
	*/
      }
    }

    cout << mfield[b][a] << endl;
    
  }
  
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
#define ALL(a)  (a).begin(),(a).end()
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<long long, long long> Pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<long long> vll;
typedef vector<vector<long long>> vvll;
template <typename T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template <typename T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL << 60;

struct prod{
  int v, w;
  prod(){}
  prod(int a, int b){v = a; w = b;}
};

vvll dp(110, vll(11000, 0));

int main(){
  int N, W;
  cin >> N >> W;
  vector<prod> p(N);
  for(int i = 0; i < N; i++){
    int a, b;
    cin >> a >> b;
    p.at(i) = prod(a, b);
  }

  for(int i = 0; i < N; i++){
    for(int j = 0; j <= W; j++){
      chmax(dp.at(i+1).at(j), dp.at(i).at(j));
      if(j >= p.at(i).w){
        chmax(dp.at(i+1).at(j), dp.at(i).at(j - p.at(i).w) + p.at(i).v);
      }
    }
  }
  cout << dp.at(N).at(W) << endl;
}


Measured memory_bytes: 12208
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>

int cmp( const void *p, const void *q ) {
    return -*(int*)p + *(int*)q;
}
//qsort(a,n,sizeof(int),cmp);

int cmp_s(const void * left, const void * right)
{
	char *left_char = (char *)left;
  char *right_char = (char *)right;
  return strcmp(left_char, right_char);
}
//qsort(s,n,sizeof(s[0]),cmp_s);

int end(void){
return 0;
}

int main (void){

int n,count=1;
  scanf("%d\n", &n);
  char s[n][11];
  for (int i = 0; i < n; i++) {
    scanf("%s", s[i]);
  }
 
  qsort(s,n,sizeof(s[0]),cmp_s);
	for (int i = 1; i < n; i++) {
		if (strcmp(s[i],s[i-1]) != 0) {
          count++;
		} 
	}
  printf("%d\n",count);
  end;

}



Measured memory_bytes: 5700
#include <iostream>
#include <math.h>
using namespace std;
int main()
{
  long long int x,ans,b=100;
  cin>>x;
  for(int i=1; ;i++){
    b*=1.01;
    if(b>=x){ans=i; break;}
  }
  cout<<ans<<endl;
    
  return 0;
}

Measured memory_bytes: 3636
object Main {
  def main(args: Array[String]): Unit = {
    import scala.io.StdIn.readLine
    val Array(datA, datB, datH, datM) = readLine.split(" ").map(_.toInt)

    val radA = (360.0 / 12) * datH + (360.0 / 12 / 60) * datM
    val radB = (360.0 / 60) * datM
    val radAB_ = math.abs(radA - radB)
    val radAB = if (radAB_ > 180) (360 - radAB_) else radAB_
    //println(radA + " " + radB + " " + radAB)
    val ans2 = (datA * datA) + (datB * datB) - (2 * datA * datB) * math.cos(radAB * (math.Pi / 180))

    val ans = math.sqrt(ans2)
    println(ans)
  }
}


Measured memory_bytes: 54700
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <sstream>
#include <string>
#define _repargs(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _repargs(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define mod 1000000007
#define inf 2000000007
#define mp make_pair
#define pb push_back
typedef long long ll;
using namespace std;
template <typename T>
inline void output(T a, int p = 0) {
    if(p) cout << fixed << setprecision(p)  << a << "\n";
    else cout << a << "\n";
}
// end of template

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    // source code
    
    string s;
    cin >> s;
    string A[4] = {"KIH", "B", "R", ""};
    rep(i, 16){
        string t = "";
        rep(j, 4){
            if((i >> j) & 1){
                t += "A";
            }
            t += A[j];
        }
//        output(t);
        if(t == s){
            output("YES");
            return 0;
        }
    }
    output("NO");
    
    return 0;
}


Measured memory_bytes: 764
#include <bits/stdc++.h>
#define whlie while
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define rep(i,N) for(int i = 0; i < (N); i++)
#define repr(i,N) for(int i = (N) - 1; i >= 0; i--)
#define rep1(i,N) for(int i = 1; i <= (N) ; i++)
#define repr1(i,N) for(int i = (N) ; i > 0 ; i--)
#define each(x,v) for(auto& x : v)
#define all(v) (v).begin(),(v).end()
#define sz(v) ((int)(v).size())
#define vrep(v,it) for(auto it = v.begin(); it != v.end(); it++)
#define vrepr(v,it) for(auto it = v.rbegin(); it != v.rend(); it++)
#define ini(...) int __VA_ARGS__; in(__VA_ARGS__)
#define inl(...) ll __VA_ARGS__; in(__VA_ARGS__)
#define ins(...) string __VA_ARGS__; in(__VA_ARGS__)
using namespace std; void solve();
using ll = long long; using vl = vector<ll>;
using vi = vector<int>; using vvi = vector< vector<int> >;
constexpr int inf = 1001001001;
constexpr ll infLL = (1LL << 61) - 1;
struct IoSetupNya {IoSetupNya() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); cerr << fixed << setprecision(7);} } iosetupnya;
template<typename T, typename U> inline bool amin(T &x, U y) { return (y < x) ? (x = y, true) : false; }
template<typename T, typename U> inline bool amax(T &x, U y) { return (x < y) ? (x = y, true) : false; }
template<typename T, typename U> ostream& operator <<(ostream& os, const pair<T, U> &p) { os << p.first << " " << p.second; return os; }
template<typename T, typename U> istream& operator >>(istream& is, pair<T, U> &p) { is >> p.first >> p.second; return is; }
template<typename T> ostream& operator <<(ostream& os, const vector<T> &v) { int s = (int)v.size(); rep(i,s) os << (i ? " " : "") << v[i]; return os; }
template<typename T> istream& operator >>(istream& is, vector<T> &v) { for(auto &x : v) is >> x; return is; }
void in(){} template <typename T,class... U> void in(T &t,U &...u){ cin >> t; in(u...);}
void out(){cout << "\n";} template <typename T,class... U> void out(const T &t,const U &...u){ cout << t; if(sizeof...(u)) cout << " "; out(u...);}
template<typename T>void die(T x){out(x); exit(0);}
#ifdef NyaanDebug
  #include "NyaanDebug.h"
  #define trc(...) do { cerr << #__VA_ARGS__ << " = "; dbg_out(__VA_ARGS__);} while(0)
  #define trca(v,N) do { cerr << #v << " = "; array_out(v , N);cout << endl;} while(0)
#else
  #define trc(...)
  #define trca(...)
  int main(){solve();}
#endif

using P = pair<double,double>; using vp = vector<P>;
constexpr int MOD = /**/ 1000000007; //*/ 998244353;
/////////////////

void solve(){
  ini(N , K);
  vi ok(10 , 1);
  rep(i , N){
    ini(j); ok[j] = 0;
  }
  while(1){
    int cur = N;
    whlie(cur){
      if(ok[cur % 10] == 0) break;
      cur /= 10;
    }
    if(cur == 0) die(N);
    N++;
  }
}

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

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


int main() {
	string s;
	cin >> s;
	stack<char> st;

	int res = 0;
	for (int i=0; i<s.size(); i++) {
		if (st.empty()) {
			st.push(s[i]);
			continue;
		}
		if (st.top()!=s[i]) {
			st.pop();
			res += 2;
		}
		else st.push(s[i]);
	}
	cout << res << endl;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    if (n < 1000)
    {
        cout <<1000- n << endl;
        return 0;
    }
    if (n % 1000 == 0)
    {
        cout << "0" << endl;
    }
    else
    {
        if (n >= 1000 and n <= 2000)
        {
            cout << 2000 - n << endl;
        }
        else if (n >= 2000 and n <= 3000)
        {
            cout << 3000 - n << endl;
        }
        else if (n >= 3000 and n <= 4000)
        {
            cout << 4000 - n << endl;
        }
        else if (n >= 4000 and n <= 5000)
        {
            cout << 5000 - n << endl;
        }
        else if (n >= 5000 and n <= 6000)
        {
            cout << 6000 - n << endl;
        }
        else if (n >= 6000 and n <= 7000)
        {
            cout << 7000 - n << endl;
        }
        else if (n >= 7000 and n <= 8000)
        {
            cout << 8000 - n << endl;
        }
        else if (n >= 8000 and n <= 9000)
        {
            cout << 9000 - n << endl;
        }
        else if (n >= 9000 and n <= 10000)
        {
            cout << 10000 - n << endl;
        }
    }
}

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

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

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

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

#define P pair<int,int>
#define I vector<int>
#define S set<int>
#define pb(v) push_back(v)
#define V vector
int main(){
    CIN(N);
    I vec(9,0);
    REP(a,N){
        CIN(b);
        if(b<=399)vec.at(0)++;
        if(400<=b&&b<=799)vec.at(1)++;
        if(800<=b&&b<=1199)vec.at(2)++;
        if(1200<=b&&b<=1599)vec.at(3)++;
        if(1600<=b&&b<=1999)vec.at(4)++;
        if(2000<=b&&b<=2399)vec.at(5)++;
        if(2400<=b&&b<=2799)vec.at(6)++;
        if(2800<=b&&b<=3199)vec.at(7)++;
        if(3200<=b)vec.at(8)++;
    }
    int mi=0,ma=0;
    REP(a,8){
        if(vec.at(a)!=0){
            mi++;
            ma++;
        }
    }
    if(mi==0){
        if(vec.at(8)==0){
            cout<<0;
        }else{
            cout<<1;
        }
    }else{
        cout<<mi;
    }
    cout<<" "<<(ma+vec.at(8))<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define forE(i,x) for(int i=head[x];i!=-1;i=ne[i])
using namespace std;
typedef long long i64;
typedef unsigned long long u64;
typedef unsigned u32;
typedef pair<int,int> pin;
#define mk(a,b) make_pair(a,b)
#define lowbit(x) ((x)&(-(x)))
#define sqr(a) ((a)*(a))
#define clr(a) (memset((a),0,sizeof(a)))
#define ls ((x)<<1)
#define rs (((x)<<1)|1)
#define mid (((l)+(r))>>1)
#define pb push_back
#define w1 first
#define w2 second
inline void read(int &x){
	x=0;int f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	x*=f;
}
inline void judge(){
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
}
/******************************head*******************************/
const int maxn=100005;
int X,K,r[maxn],Q,a,b,c,d;
inline void add(int v){
	c+=v;
	if(a>X-c)a=b=X-c;
	else b=b>X-c?X-c:b;
	if(b<-c)a=b=-c;
	else a=a<-c?-c:a;
}
int main(){
	read(X);read(K);
	rep(i,1,K)read(r[i]);
	a=0;b=X;c=d=0;
	read(Q);int j=1,k=-1;
	rep(i,1,Q){
		int t,x;read(t);read(x);
		for(;j<=K&&r[j]<=t;d=r[j++],k=-k)add(k*(r[j]-d));
			add(k*(t-d));d=t;
		int res;
		if(x<a)res=a+c;else if (x<=b)res=x+c;else res=b+c;
		printf("%d\n",res);
	}
	return 0;
}


Measured memory_bytes: 1536
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <utility>
#include <cstdio>
#include <iomanip>
#include <cmath>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <stdlib.h>
#include <set>
typedef long long ll;
using namespace std;

int main() {
	int a,b,sum=1,cnt=0;
	cin>>a>>b;
	while(sum<b){
		sum--;
		cnt++;
		sum+=a;
	}
	cout << cnt << endl;
	return 0;
}



Measured memory_bytes: 256
#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
template<class T>
using Table = vector<vector<T>>;
const ld eps=1e-9;

//// < "D:\D_Download\Visual Studio 2015\Projects\programing_contest_c++\Debug\a.txt"
map<vector<vector<int>>, int>mp;

vector<vector<int>>goal;

int getans(const vector<vector<int>>&field) {
	if (field == goal)return 0;
	auto it = mp.find(field);
	if (it != mp.end())return it->second;
	else {
		int ans = 1e5;
		vector<vector<int>>nfield(field);
		for (int i = 0; i < 4; ++i) {
			for (int j = 1; j < 8; ++j) {
				if (!field[i][j]) {
					int from = field[i][j - 1];
					for (int k = 0; k < 4; ++k) {
						for (int l = 0; l < 8; ++l) {
							if (nfield[k][l] == from + 1) {
								swap(nfield[i][j], nfield[k][l]);
								ans = min(getans(nfield) + 1,ans);
								swap(nfield[i][j], nfield[k][l]);
							}
						}
					}
				}
			}
		}
		return mp[field] = ans;
	}
}
int main() {
	int N; cin >> N;
	while (N--) {
		mp.clear();
		vector<vector<int>>field(4, vector<int>(8));
		goal = field;
		for (int i = 0; i < 4; ++i) {
			for (int j = 0; j < 7; ++j) {
				goal[i][j] = 10 * (i + 1) + j + 1;
			}
		}
		for (int i = 0; i < 4; ++i) {
			field[i][0] = i * 10 + 11;
			for (int j = 0; j < 7; ++j) {
				int a; cin >> a;
				if (a % 10 != 1) {
					field[i][j + 1] = a;
				}
			}
		}
		int ans = getans(field);
		if (ans > 9999)ans = -1;
		cout << ans << endl;

	}
	
	
	return 0;
}

Measured memory_bytes: 27660
#include<stdio.h>
int main(void){
    int x;
    scanf("%d",&x);
    switch(x%7){
        case 1 : printf("fri\n"); break;
        case 2 : printf("sat\n"); break;
        case 3 : printf("sun\n"); break;
        case 4 : printf("mon\n"); break;
        case 5 : printf("tue\n"); break;
        case 6 : printf("wed\n"); break;
        case 0 : printf("thu\n"); break;
    }
	return 0;		
}


Measured memory_bytes: 2692
#include<iostream>
#include<algorithm>
#include<deque>
using namespace std;
int main(){
int n,k; cin >> n >> k;
int h[100000];for(int i = 0; i < n; i++) cin >> h[i];
int dp[100000];
deque<int> q;
dp[0] = 0;
for(int i = 1; i < n; i++){
        for(int j = 0;(j < k && j < i); j++){
               q.push_back(dp[i - j - 1] + abs(h[i] - h[i - j - 1]));
               }
        sort(q.begin(), q.end());
        dp[i] = q.front();
        q.clear();
}
cout << dp[n - 1] << "\n";
}

Measured memory_bytes: 1024
N = int(input())
H = list(map(int,input().split()))
b = [0]*N
mb = 0
for i in range(N-2,-1,-1):
    if H[i+1] <= H[i]:
        b[i] = b[i+1]+1
    else:
        b[i]= 0
    mb = max(mb,b[i])
print(mb)


Measured memory_bytes: 20432
n, k = map(int, input().split())
buckets = [0]*(10**5)

for i in range(n):
  a, b = map(int, input().split())
  buckets[a-1] += b

for i in range(10**5):
  k -= buckets[i]
  if(k <= 0):
    print(i+1)
    break

Measured memory_bytes: 5748
#include <iostream>
#include <math.h>
#include <algorithm>
#include <functional>
#include <vector>
#include <typeinfo>
#include <climits>
#include <ctype.h>
#include <string>
#include <stack>
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, n) for (int i = a; i < n; i++)
#define REP(i, n) for(int i = 0; i < n; i++)
struct omt{omt(){ios::sync_with_stdio(false);cin.tie(0);}}star;

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

    int cnt = 0;
    REP(i, n){
        int l, r;
        cin >> l >> r;
        cnt += r - l + 1;
    }
    cout << cnt << endl;


    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<sstream>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<complex>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cassert>

#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define mp make_pair
#define pb push_back
#define each(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define dbg(x) cerr<<__LINE__<<": "<<#x<<" = "<<(x)<<endl

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
const int inf = (int)1e9;
const double INF = 1e12, EPS = 1e-9;

int n, m, dist[200][200], p[200];
int x[100], y[100], vv[100], xx[100], yy[100];
double d[100][100];
bool v[200];

bool rec(int s, int k){
	if(s < 0) return 1;
	rep(i, n + m) if(dist[s][i] >= 0 && dist[s][i] < k && !v[i]){
		v[i] = 1;
		if(rec(p[i], k)) return p[s] = i, p[i] = s, 1;
	}
	return 0;
}
bool ok(int k){
	rep(i, n + m) p[i] = -1;
	int res = 0;
	rep(i, n + m) if(p[i] < 0){
		rep(j, n + m) v[j] = 0;
		if(rec(i, k)) res++;
	}
	return res >= m;
}

int main(){
	while(cin >> n >> m, n){
		rep(i, n) cin >> x[i] >> y[i] >> vv[i];
		rep(i, m) cin >> xx[i] >> yy[i];
		
		vector<double> v;
		rep(i, n) rep(j, m){
			d[i][j] = hypot(x[i] - xx[j], y[i] - yy[j]) / vv[i];
			v.pb(d[i][j]);
		}
		sort(all(v));
		v.erase(unique(all(v)), v.end());
		memset(dist, -1, sizeof(dist));
		rep(i, n) rep(j, m) dist[i][j + n] = dist[j + n][i] = lower_bound(all(v), d[i][j] - EPS) - v.begin();
		
		int lo = 0, hi = v.size(), mid;
		while(lo + 1 < hi){
			mid = (lo + hi) / 2;
			if(ok(mid)) hi = mid;
			else lo = mid;
		}
		printf("%.9f\n", v[hi - 1]);
	}
	return 0;
}

Measured memory_bytes: 1628
n = int(input())
from collections import defaultdict
d = defaultdict(int)

for i in range(1,min(n,100)):
	for j in range(1,min(n,100)):
		for k in range(1,min(n,100)):
			if i+j+k <= 150:
				p = (i+j+k)**2-(i*j)-(j*k)-(i*k)
				d[p]+=1

for i in range(1,n+1):
	print(d[i])


Measured memory_bytes: 10280
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<queue>
#include<vector>
#include<functional>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<numeric>
#include<limits>
#include<iterator>

#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define rep(i,n) for(int i=0; i<n; i++)

using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ll, char> plc;

ll x[210][210];
ll INF = (ll)(1e10);

int main()
{
	int n, m, r;
	ll ans = INF;
	cin >> n >> m >> r;

	vector<int> R(r);

	rep(i, r) cin >> R[i];

	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++)
		x[i][j] = x[j][i] = INF;


	rep(i, m) {
			ll a, b, c;
			cin >> a >> b >> c;
			x[a][b] = min(x[a][b], c);
			x[b][a] = x[a][b];
	}
	
	sort(R.begin(), R.end());
	

	for(int k=1; k<=n; k++)
		for(int i=1; i<=n; i++)
			for(int j=1; j<=n; j++)
				x[i][j] = min(x[i][j], x[i][k] + x[k][j]);
	
	do {
 		ll sum = 0,pre = R[0];
		for (int i = 1; i < r; i++) {
			sum += x[pre][R[i]];
			pre = R[i];
		}
		ans = min(ans, sum);
	} while (next_permutation(R.begin(), R.end()));

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


Measured memory_bytes: 512
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#include <list>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;

int main()
{
	string s, t; cin>>s>>t;
	int ans=0;
	for(int i=0; i<s.size(); i++){
		if(s[i]!=t[i]) ans++;
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 3916
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

#define debug(x) cerr<<#x<<'='<<x<<'\n'
#define Int const int &

char h[55][55]; 

int main(void) {
	
	int n, m;
	cin>>n>>m;
	for (int i=1; i<=n; i++) {
		for (int j=1; j<=m; j++) {
			cin>>h[i][j];
		}
	}
	for (int i=1; i<=n; i++) {
		for (int j=1; j<=m; j++) {
			if (h[i][j]!='#') {
				h[i][j]='0';
				h[i][j]+=(int)(h[i-1][j]=='#')+(int)(h[i-1][j+1]=='#')+(int)(h[i-1][j-1]=='#');
				h[i][j]+=(int)(h[i+1][j]=='#')+(int)(h[i+1][j+1]=='#')+(int)(h[i+1][j-1]=='#');
				h[i][j]+=(int)(h[i][j-1]=='#')+(int)(h[i][j+1]=='#');
			}
			printf("%c", h[i][j]);
		}
		cout<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
struct abc {
    long long v;
    int id;
    bool operator < (const abc &a) const {
        return v > a.v;
    }
}a[2010];
long long f[2010][2010];
int main() {
    int n, i, l, r;
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        a[i].id = i;
    }
    sort(a, a + n);
    for (i = 0; i < n; i++) {
        for (l = 0; l <= i; l++) {
            r = n - 1 - (i - l);
            f[i+1][l+1] = max(f[i+1][l+1], f[i][l]+a[i].v*abs(l-a[i].id));
            f[i+1][l] = max(f[i+1][l], f[i][l]+a[i].v*abs(r-a[i].id));
        }
    }
    long long ans = 0;
    for (i = 0; i <= n; i++) ans = max(ans, f[n][i]);
    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 24416
/*********************
*					 *	
* Nothing Impossible *
*					 *
*********************/
#include <algorithm>
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <cmath>
#define GetRand(Min, Max) ((rand()%(int)(((Max) + 1)-(Min))) + (Min))
#define Rep(i, min, max) for (int i = min; i < max; ++i)
#define PB push_back
using namespace std;

int main()
{
	int a, b;
	cin >> a >> b;
	if(a>9||b>9)	cout << "-1" << endl;
	else cout << a*b;
	return 0;
}

Measured memory_bytes: 256
A, B, C, D = map(int, input().split())

i = 0
while True:
  if i % 2 == 0:
    C -= B
    if C <= 0:
      print("Yes")
      break
  else:
    A -= D
    if A <= 0:
      print("No")
      break
  i += 1

Measured memory_bytes: 9048
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0563"

#include<bits/stdc++.h>
using namespace std;

#define call_from_test
#ifndef call_from_test
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
#endif
//BEGIN CUT HERE
struct FastIO{
  FastIO(){
    cin.tie(0);
    ios::sync_with_stdio(0);
  }
}fastio_beet;
//END CUT HERE
#ifndef call_from_test
signed main(){
  return 0;
}
#endif

#ifndef call_from_test
#include<bits/stdc++.h>
using namespace std;
#endif
//BEGIN CUT HERE
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/tag_and_trait.hpp>
using namespace __gnu_pbds;
template <typename T>
using gtree = tree<T,null_type,less<T>,rb_tree_tag,
                   tree_order_statistics_node_update>;
// usage:
// find_by_order(int k):
// return the iterator of k-th smallest element (0-indexed)
// order_of_key(T key):  return the index of key in tree
//END CUT HERE
#ifndef call_from_test
signed ARC028_B(){
  using ll = long long;
  int n,k;
  cin>>n>>k;
  vector<int> xs(n);
  for(int i=0;i<n;i++) cin>>xs[i];
  map<int, int> mp;
  for(int i=0;i<n;i++) mp[xs[i]]=i+1;
  gtree<ll> G;
  for(int i=0;i<k-1;i++) G.insert(xs[i]);
  for(int i=k-1;i<n;i++){
    G.insert(xs[i]);
    auto key=*G.find_by_order(k-1);
    cout<<mp[key]<<endl;
  }
  return 0;
}

/*
  verified on 2019/12/09
  https://atcoder.jp/contests/arc028/tasks/arc028_2
*/

signed ARC033_C(){
  int q;
  cin>>q;
  gtree<int> G;
  while(q--){
    int t,x;
    cin>>t>>x;
    if(t==1) G.insert(x);
    if(t==2){
      int k=*G.find_by_order(x-1);
      G.erase(k);
      cout<<k<<endl;
    }
  }
  return 0;
}

/*
  verified on 2019/12/09
  https://atcoder.jp/contests/arc033/tasks/arc033_3
*/

signed main(){
  //ARC028_B();
  //ARC033_C();
  return 0;
}
#endif

#undef call_from_test

signed main(){
  using ll = long long;

  int w,h,n;
  cin>>w>>h>>n;
  vector<int> xs(n),ys(n);
  for(int i=0;i<n;i++) cin>>xs[i]>>ys[i];

  using P = pair<int, int>;
  gtree<P> gx,gy;
  for(int i=0;i<n;i++){
    gx.insert(P(xs[i],i));
    gy.insert(P(ys[i],i));
    gx.insert(P(xs[i],n+i));
    gy.insert(P(ys[i],n+i));
  }

  ll ans=1e18;
  int ax=-1,ay=-1;

  map<int, ll> mx,my;

  for(int i=0;i<n;i++){
    gx.erase(P(xs[i],i));
    gy.erase(P(ys[i],i));


    int tx=gx.find_by_order(n-1)->first;
    int ty=gy.find_by_order(n-1)->first;

    if(!mx.count(tx)){
      mx[tx]=0;
      for(int j=0;j<n;j++)
        mx[tx]+=abs(xs[j]-tx)*2;
    }

    if(!my.count(ty)){
      my[ty]=0;
      for(int j=0;j<n;j++)
        my[ty]+=abs(ys[j]-ty)*2;
    }

    ll res=mx[tx]+my[ty]-(abs(xs[i]-tx)+abs(ys[i]-ty));
    if((res< ans)||
       (res==ans&&tx< ax)||
       (res==ans&&tx==ax&&ty< ay)){
      ans=res;
      ax=tx;
      ay=ty;
    }


    gx.insert(P(xs[i],i));
    gy.insert(P(ys[i],i));
  }

  cout<<ans<<endl;
  cout<<ax<<" "<<ay<<endl;
  return 0;
}



Measured memory_bytes: 28728
dic = {"": 0}

n = int(input())
for i in range(n):
  inp = input()
  if inp in dic:
    dic[inp] += 1
  else:
    dic[inp] = 1

m = int(input())
for i in range(m):
  inp = input()
  if inp in dic:
    dic[inp] -= 1
  else:
    dic[inp] = -1

print(max(dic.values()))

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

#define rep(i,n) for(ll i = 0; i < n; i++)
#define REP(i,n) for(ll i = 1; i < n; i++)
#define sz(x) ll(x.size())
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define YesorNo(a) printf(a ? "Yes\n" : "No\n")
#define endl '\n'
using ll = long long;
using P = pair<ll,ll>;
using Pl = pair<ll,ll>;
using vi = vector<ll>;
using vii = vector<vi>;
using vl = vector<ll>;
using vll = vector<vl>;
using vs = vector<string>;
using vb = vector<bool>;
using vc = vector<char>;
using vcc = vector<vc>;
const ll dx[] = {0,1,0,-1,1,1,-1,-1};
const ll dy[] = {1,0,-1,0,1,-1,-1,1};
const ll inf = (1<<30)-1;
const ll infll = (1LL<<62)-1;
ll ceil(const ll &a, const ll &b){return ((a)+(b)-1)/b;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

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

  ll n;
  cin >> n;
  vi a(n);
  rep(i,n) cin >> a[i];
  vi ans(n);
  ll m = 0;
  for(ll i = n-1; i >= 0; i--) {
    ll sum = 0;
    for(ll j = 2; (i+1)*j <= n; j++) {
      sum += ans[(i+1)*j-1];
    }
    sum %= 2;
    if(sum != a[i]) {
      m++;
      ans[i]++;
    }
  }
  cout << m << endl;
  rep(i,n) {
    if(ans[i]) cout << i+1 << ' ';
  }
}

Measured memory_bytes: 3968
#include "bits/stdc++.h"
#define rep(i,n) for(int i=0;i<n;i++)
#define ALL(v) (v).begin(),(v).end()
typedef long long LL;
const int INF = 1 << 25;
const LL MOD = 1000000007LL;
using namespace std;
typedef pair<int, int> P;
char S[2][53];
int main() {
	int N;
	cin >> N;
	cin >> S[0] >> S[1];
	vector<int> domino;
	rep(i, N) {
		if (S[0][i] == S[1][i]) {
			domino.push_back(0);
		}
		else {
			domino.push_back(1);
			i++;
		}
	}
	LL ans;
	if (domino[0]) ans = 6;
	else ans = 3;
	for (int i = 1; i < domino.size(); i++) {
		if (domino[i - 1]) {
			if (domino[i]) (ans *= 3) %= MOD;
		}
		else {
			(ans *= 2) %= MOD;
		}
	}
	cout << ans << endl;
}

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

int main() {
  char c;
  cin >> c;
  
  if (c == 'a' or c == 'i' or c == 'u' or c == 'e' or c == 'o')
    cout << "vowel" << endl;
  else
    cout << "consonant" << endl;
}


Measured memory_bytes: 3560
X = int(input())
N = X//100
X %=100
if N == 0:
    print(0)
    exit()
if X == 0:
    print(1)
    exit()
for i in [5,4,3,2,1]:
    for j in range(N,0,-1):
        if X//(i*j) > 0:
            N -= j
            X %= i*j
            break
    if N == 0:
        break
if X == 0:
    print(1)
else:
    print(0)

Measured memory_bytes: 3064
#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <numeric>
#include <iterator>

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int,int> PII;
typedef istringstream ISS;
typedef ostringstream OSS;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( v, c ) for ( auto &v : c )

#define EACH( it, c ) for ( auto it = c.begin(); it != c.end(); ++it )
#define ALL( c ) (c).begin(), (c).end()
#define DRANGE( c, p ) (c).begin(), (c).begin() + p, (c).end()

#define PB( n ) push_back( n )
#define MP( a, b ) make_pair( ( a ), ( b ) )
#define EXIST( c, e ) ( (c).find( e ) != (c).end() )

#define fst first
#define snd second

#define DUMP( x ) cerr << #x << " = " << ( x ) << endl
#define DEBUG( x ) cerr << __FILE__ << ":" << __LINE__ << ": " << #x << " = " << ( x ) << endl

const int PLUS[] = { -1, 1 };

VI solve( int num )
{
	vector<bool> isPrime( num + 1, true );
	VI res;

	for ( int n = 1; 7 * n - 1 <= num; n++ )
	{
		REP( i, 0, 2 )
		{
			const int p = 7 * n + PLUS[i];

			if ( !( num % p ) && isPrime[p] )
			{
				res.PB( p );
				for ( int j = 1; p * j <= num; j++ )
				{
					isPrime[ p * j ] = false;
				}
			}
		}
	}

	return res;
}

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

	for ( int num; cin >> num, num != 1; )
	{
		VI res = solve( num );
		cout << num << ':';
		REP( i, 0, res.size() )
		{
			cout << ' ' << res[i];
		}
		cout << endl;
	}

	return 0;
}

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

int N, U[100000], V[100000], W[100000];
int ans[100001];
vector< vector< pair<int, int> > > G(100001);

void dfs(vector< pair<int, int> > v, int color){
    if( v.empty() ) return;

    for(int i=0;i<v.size();i++){
        if( ans[ v[i].first ] == -1 ){
            int res = color;
            if( v[i].second % 2 == 1 )  res = 1 - color;
            ans[ v[i].first ] = res;
            dfs(G[ v[i].first ], res);
        }
    }
    return;
}

int main(){
    cin >> N;
    for(int i=0;i<N-1;i++)  cin >> U[i] >> V[i] >> W[i];

    for(int i=0;i<N-1;i++){
        G[ U[i] ].push_back( make_pair(V[i], W[i]) );
        G[ V[i] ].push_back( make_pair(U[i], W[i]) );
    }

    for(int i=1;i<=N;i++)   ans[i] = -1;
    int color = 0;
    ans[1] = color;
    dfs(G[1], color);

    for(int i=1;i<=N;i++)   cout << ans[i] << endl;
}

Measured memory_bytes: 13440
n,m=map(int,input().split())
imos=[0]*(10**5+10)
maxr=-1
for _ in range(m):
    l,r=map(int,input().split())
    imos[l]+=1
    imos[r+1]-=1
    maxr=max(maxr,r)

for i in range(maxr+1):
    imos[i+1]+=imos[i]

ans=0

for i in range(maxr+1):
    if imos[i]==m:
        ans+=1

print(ans)


Measured memory_bytes: 6900
import numpy as np
n=int(input())
k=0
def f(a,b):
  if a < b:
    a,b=b,a
  while True:
    if a%b==0:
      return b
    else:
      a,b=b,a%b
for a in range(1,n+1):
  for b in range(1,a+1):
    for c in range(1,b+1):
      m=f(f(a,b),c)
      if a==b and b==c:
        k+=m
      elif a==b or b==c:
        k+=3*m
      else:
        k+=6*m
print(k)

Measured memory_bytes: 27132
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<deque>
#include<map>
#include<bitset>

using namespace std;
using ll = long long;

#define rep(i, n) for(int i = 0;i < (n);i++)
#define repr(i, n) for(int i = (n);i >= 0;i--)
#define repf(i, m, n) for(int i = (m);i < (n);i++)

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;}
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
//////////////////////////////////////////////////

int n, K;
int a[110];
bool dp[100010];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> K;
    rep(i, n) cin >> a[i];
    memset(dp, false, sizeof(dp)); 
    rep(k, K+1) {
        rep(i, n) {
            if (k >= a[i]) {
                dp[k] |= !dp[k - a[i]];
            }
        }
    }
    cout << (dp[K] ? "First" : "Second") << endl;
    return 0;
}



Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <queue>

using namespace std;


int main() {
	int n;
	cin >> n;
	vector<vector<int>> to(n), cost(n);
	queue<int> q;
	vector<int> ans(n, -1);

	for (int i = 0; i < n-1; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		a--;
		b--;
		to[a].emplace_back(b);
		cost[a].emplace_back(c);
		to[b].emplace_back(a);
		cost[b].emplace_back(c);
	}

	ans[0] = 0;
	q.push(0);
	while (!q.empty()) {
		int tmp = q.front();
		q.pop();
		for (int i = 0; i < to[tmp].size(); i++) {
			int tmp1 = to[tmp][i];
			int tmp2 = cost[tmp][i];
			if (ans[tmp1] != -1) continue;
			ans[tmp1] = (tmp2 + ans[tmp])%2;
			q.push(tmp1);
		}
	}

	for (auto i : ans) {
		cout << i << endl;
	}

	return 0;
}

Measured memory_bytes: 11904
#include <iostream>
#include <cstdio>
#include <cmath>
#include <climits>
using namespace std;

int main(){
  int n,tmp;
  cin>>n;
  bool flag;
  for(int i = 1; i <= n; i++){
    flag = false;
    if(i % 3 == 0) flag = true;
    tmp = i;
    while(tmp){
      if(tmp % 10 == 3) flag = true;
      tmp /= 10;
    }
    if(flag){
      cout<<' '<<i;
    }
  }
  cout<<endl;

  return 0;
}

Measured memory_bytes: 3064
#include <stdio.h>

main(){
        int a,b;

        while(scanf("%d %d",&a,&b)!=EOF){
                a+=b;
                b=1;
                while(a/=10)b++;//printf("%d\n",a%=10);
                printf("%d\n",b++);
        }
        return 0;
}

Measured memory_bytes: 600
#include <bits/stdc++.h>
using namespace std;
int main () {
	string s;
	cin >> s;
	int cnt = 0, Ans = 0;
	for(int i = 0; i < 3; i++) {
		if(s[i] == 'R') {
			++cnt;
		}
		else {
			cnt = 0;
		}
		Ans = max(Ans, cnt);
	}
	cout << Ans << endl;
	return 0;
}

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

int main() {
  string S;
  cin >> S;
  bool ans = true;
  if (S.at(0) != 'A') {
    ans = false;
  }
  int cnt = 0;
  for (int i = 1; i < S.size(); ++i) {
    if (isupper(S.at(i))) {
      if (i == 1 || i == S.size() - 1 || S.at(i) != 'C') {
        ans = false;
      }
      ++cnt;
    }
  }
  if (cnt != 1) {
    ans = false;
  }
  if (ans) {
    cout << "AC" << endl;
  } else {
    cout << "WA" << endl;
  }
}


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

void solve()
{
    string s,t;
    cin>>s>>t;
    int n=s.length(),m=t.length();
    int dp[n+1][m+1];
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            if(i==0||j==0)
                dp[i][j]=0;
            else if(s[i-1]==t[j-1])
                dp[i][j]=1+dp[i-1][j-1];
            else
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    }
    int index=dp[n][m];
    char ans[index+1];
    ans[index]='\0';
    int i=n,j=m;
    while(i>0 && j>0)
    {
        if(s[i-1]==t[j-1])
        {
            ans[index-1]=s[i-1];
            index--,i--,j--;
        }
        else if(dp[i-1][j]>dp[i][j-1])
            i--;
        else
            j--;
    }
    cout<<ans<<"\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    solve();
    return 0;
}

Measured memory_bytes: 35456
package main

import "fmt"

func main() {
	var x, y int
	fmt.Scan(&x, &y)

	ok := false
	for i := 0; i <= x; i++ {
		if 2*i+4*(x-i) == y {
			ok = true
			break
		}
	}

	if ok == true {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}

Measured memory_bytes: 1756
N, K = map(int, input().split())
mod = 10**9 + 7

def com(n, r):
    p, q = 1, 1
    for i in range(r):
        p = p*(n-i)%mod
        q = q*(r-i)%mod
    return p*pow(q, mod-2, mod)%mod

for k in range(1, K+1):
    print(com(N-K+1, k)*com(K-1, k-1)%mod)

Measured memory_bytes: 3316
#include<bits/stdc++.h>
using namespace std;
 
int main(){
  string S,T,U;
  int A,B;
  cin >> S >> T;
  cin >> A >> B;
  cin >> U;
  if(U == S) cout << A-1 << " " << B << endl;
  else if(U == T) cout << A << " " << B-1 << endl;
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#define MOD 1000000007

long	my_pow(long  x, long n)
{
	if (n == 0)
		return (1);
	if (n % 2 == 0)
		return ((my_pow((x * x) % MOD, n / 2)) % MOD);
	if (n % 2 == 1)
		return ((my_pow((x * x) % MOD, n / 2) * x) % MOD);
	return (1);
}

int		factorial(int n)
{
	if (n < 0)
		return (0);
	if (n < 1)
		return (1);
	return ((int)(((long)n * factorial(n - 1)) % MOD));
}

int		inverse(int nb)
{
	return ((int)(my_pow(nb, MOD - 2) % MOD));
}

int		comb(int m, int n)
{
	int		i;
	long	comb;

	comb = 1;
	i = m - n + 1;
	while (i <= m)
	{
		comb *= i++;
		comb %= MOD;
	}
	comb *= inverse(factorial(n));
	comb %= MOD;
	return ((int)comb);
}

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

	if ((scanf("%d %d %d", &n, &a, &b)) < 3)
		return (-1);
	ans = (((int)my_pow(2, (long)n) - 1 - comb(n, a)) % MOD - comb(n, b)) % MOD;
	if (ans < 0)
		ans += MOD;
	printf("%d", ans);
}


Measured memory_bytes: 3328
"""
Writer: SPD_9X2
https://atcoder.jp/contests/dwacon6th-prelims/tasks/dwacon6th_prelims_d
左からおいていくことを考える
残ったカード全てから嫌われている場合、もう置くしかない
貪欲に置いていき、残りカード全てから嫌われてしまったら置く？

そうなるとただの実装難問題だが…

for i in range(N)
    if 残りのカード全てから嫌われてしまっているカードがあったら置く。
    elif 辞書順最小のカードが置けたら置く
    elif 辞書順2番目のカードが存在したら置く。
    else -1?

なのか？？
3枚以上なら絶対置くことが可能そうに見える


残りのカード全てから嫌われてしまっている、判定はどうすればよいと？
嫌われてる辞書(残存するカードのみ)を作っておき、len(辞書) == 2 で、1でない方が嫌われ者

elif 以降はheapqを使うのが良さそう
おいてるフラグ配列を管理しておき、置いてないが出るまでpop
置けない場合は、もう1つ出るまでpopし、置いて最初の奴を戻す

何が問題なんだ…？
この方法だとqueueが空になってしまうけど構成不可能ではない、ケースが存在する
N==2で-1は正しかった
互いに嫌いな2個が最後に残るとまずい
→最後の3つを全探索するか？
→これが丸そう
"""

def allserch(dnt,x,y,z):

    ret = []
    if dnt != x and a[x] != y and a[y] != z:
        ret.append([x,y,z])
    if dnt != x and a[x] != z and a[z] != y:
        ret.append([x,z,y])
    if dnt != y and a[y] != x and a[x] != z:
        ret.append([y,x,z])
    if dnt != y and a[y] != z and a[z] != x:
        ret.append([y,z,x])
    if dnt != z and a[z] != x and a[x] != y:
        ret.append([z,x,y])
    if dnt != z and a[z] != y and a[y] != x:
        ret.append([z,y,x])
    ret.sort()
    return ret[0]


import heapq
import sys

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

if N == 2:
    print (-1)
    sys.exit()

for i in range(N):
    a[i] -= 1

ans = []
dont = None

hq = []
for i in range(N):
    heapq.heappush(hq,i)
    
usable = [True] * N
dic = {}
for i in range(N):
    if a[i] not in dic:
        dic[a[i]] = 1
    else:
        dic[a[i]] += 1


for loop in range(N-3):

    flag = True
    
    if len(dic) == 2:
        maxind = None

        for i in dic:
            if maxind == None:
                maxind = i
            elif dic[i] > dic[maxind]:
                maxind = i

        if dic[maxind] == (N-loop-1) and usable[maxind]:
            nc = maxind
            flag = False

    if flag:

        while (not usable[hq[0]]):
            heapq.heappop(hq)
            
        fi = heapq.heappop(hq)
        if dont != fi:
            nc = fi
        else:

            while (not usable[hq[0]]):
                heapq.heappop(hq)

            
            sec = heapq.heappop(hq)
            heapq.heappush(hq,fi)
            nc = sec

    #print (nc,a[nc])
    ans.append(nc+1)
    usable[nc] = False
    dic[a[nc]] -= 1
    dont = a[nc]
    if dic[a[nc]] == 0:
        del dic[a[nc]]

pas = []
while len(hq) > 0:
    now = heapq.heappop(hq)
    if usable[now]:
        pas.append(now)

rec = allserch(dont,pas[0],pas[1],pas[2])
for i in range(3):
    rec[i] += 1
ans += rec

print (*ans)     
  

Measured memory_bytes: 80360
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define ll long long
#define ld long double
#define PB push_back
#define lc 2 * v
#define rc 2 * v + 1
#define mid (s + e) / 2
#define pii pair <int , int>
#define pll pair <long long , long long>
#define FAST ios::sync_with_stdio(false);cin.tie(0);
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

const ll maxn = 3000 + 20 , N = 60000 + 20 , mod = 1e9 + 7 , INF = 1e9 , lg = 32;

ll dp[maxn][maxn][4] , gp[maxn][maxn];
ll a[maxn][maxn] , R , C , k;

int main() {
    FAST
    cin >> R >> C >> k; R--; C--;
    for (int i = 0; i < k; ++i) {
        ll r , c , v;
        cin >> r >> c >> v;
        r--; c--;
        a[r][c] = v;
    }
    for (int i = 0; i < maxn; ++i) {
        for (int j = 0; j < maxn; ++j) {
            if(!i && !j) {
                if(a[i][j]) {
                    dp[i][j][1] = a[i][j];
                    gp[i][j] = a[i][j];
                }
            }
            else {
                if(j) {
                    dp[i][j][0] = max(dp[i][j][0] , dp[i][j - 1][0]);
                    dp[i][j][1] = max(dp[i][j][1] , dp[i][j - 1][1]);
                    if(a[i][j])
                        dp[i][j][1] = max(dp[i][j][1] , dp[i][j - 1][0] + a[i][j]);
                    dp[i][j][2] = max(dp[i][j][2] , dp[i][j - 1][2]);
                    if(a[i][j])
                        dp[i][j][2] = max(dp[i][j][2] , dp[i][j - 1][1] + a[i][j]);
                    dp[i][j][3] = max(dp[i][j][3] , dp[i][j - 1][3]);
                    if(a[i][j])
                        dp[i][j][3] = max(dp[i][j][3] , dp[i][j - 1][2] + a[i][j]);
                    for (int t = 0; t < 4; ++t) {
                        gp[i][j] = max(gp[i][j] , dp[i][j][t]);
                    }
                }
                if(i) {
                    dp[i][j][0] = max(dp[i][j][0] , gp[i - 1][j]);
                    if(a[i][j]) {
                        dp[i][j][1] = max(dp[i][j][1] , gp[i - 1][j] + a[i][j]);
                    }
                    for (int t = 0; t < 4; ++t) {
                        gp[i][j] = max(gp[i][j] , dp[i][j][t]);
                    }
                }
            }
        }
    }
    cout << gp[R][C] << '\n';
}


Measured memory_bytes: 430504
#include <stdio.h>
int main(void)
{
    int p, q, r, a, b, c;

    scanf("%d%d%d", &p, &q, &r);

    a = p + q;
    b = q + r;
    c = r + p;

    if(a <= b && a <= c) printf("%d\n", a);
    else if(b <= a && b <= c) printf("%d\n", b);
    else if(c <= a && c <= b) printf("%d\n", c);

    return 0;
    
}


Measured memory_bytes: 128
import sys

def sieve_of_eratosthenes(n=5 * 10 ** 6):
  sieve = [1] * (n + 1); sieve[0] = sieve[1] = 0
  for i in range(2, int(n ** 0.5) + 1):
    if not sieve[i]: continue
    for j in range(i * 2, n, i): sieve[j] = 0
  prime_numbers = [i for i in range(2, n + 1) if sieve[i]]
  return sieve, prime_numbers

is_prime, prime_numbers = sieve_of_eratosthenes(10 ** 3)

def prime_factorize(n):
  res = dict()
  if n < 2: return res
  border = int(n ** 0.5)
  for p in prime_numbers:
    if p > border: break
    while n % p == 0: res[p] = res.get(p, 0) + 1; n //= p
    if n == 1: return res
  res[n] = 1
  return res

def prime_factorize_factorial(n):
  res = dict()
  for i in range(2, n + 1):
    for p, c in prime_factorize(i).items(): res[p] = res.get(p, 0) + c
  return res

MOD = 10 ** 9 + 7

n = int(sys.stdin.readline().rstrip())

def main():
  res = 1
  for c in prime_factorize_factorial(n).values():
    res *= c + 1; res %= MOD
  print(res)

if __name__ ==  '__main__':
  main()

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
int v[1000];
void m(int x,int pri)
{
	if(x==1)return;
	while(x%pri!=0)pri++;
	v[pri]++;
	m(x/pri,pri);
}
int main()
{
	int n;
	cin>>n;
	for(int i=2;i<=n;i++)
		m(i,2);
	long long ans=1;
	const int MOD=1000000007;
	for(int i=2;i<=1000;i++)
		ans=ans*(v[i]+1)%MOD;
	cout<<ans;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    n = int(input())
    a = list(map(int, input().split()))
    s = sum(a)
    t = [0] * n
    for i in range(n-1):
        t[i+1] = t[i] + a[i]
    print(min(abs(s-2*t[i]) for i in range(1, n)))


if __name__ == '__main__':
    main()


Measured memory_bytes: 24612
#include <iostream>
#include <cassert>
#include <queue>

#define INF 922337203685477580
typedef long long ll;

using namespace std;

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

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

  ll op = 0LL;
  ll sum = 0LL;

  // positive
  for (int i = 0; i < n; i++) {
    sum += a[i];

    if (i % 2 == 0 && sum <= 0) {
      op += 1 - sum;
      sum = 1;
    } else if (i % 2 == 1 && sum >= 0) {
      op += sum + 1;
      sum = -1;
    }
  }

  ll op_m = op;
  sum = 0LL;
  op = 0LL;
  // negative
  for (int i = 0; i < n; i++) {
    sum += a[i];

    if (i % 2 == 1 && sum <= 0) {
      op += 1 - sum;
      sum = 1;
    } else if (i % 2 == 0 && sum >= 0) {
      op += sum + 1;
      sum = -1;
    }
  }

  op = min(op, op_m);
  cout << op << endl;
  return 0;
}


Measured memory_bytes: 1024
from itertools import product
import numpy as np
MOD = 1000000007

H,W,K = map(int,input().split())
K -= 1

transition = [[0]*W for _ in range(W)]
for edges in product((False,True),repeat=W-1):

  flag = False
  for e in edges:
    if flag and e:
      break
    flag = e
  else:
    flag = False

  if flag:
    continue

  memo = list(range(W))

  for i,e in enumerate(edges):
    if e:
      memo[i] = i+1
      memo[i+1] = i
  for i,j in enumerate(memo):
    transition[i][j] += 1


transition = np.array(transition,dtype=np.int64)


dp = np.zeros((W,1),dtype=np.int64)
dp[0,0] = 1

for h in range(H):
  dp = transition.dot(dp) % MOD

print(dp[K,0])

Measured memory_bytes: 12492