akhauriyash/Code-Regression huggingface dataset:
/* monkukui 競技プログラミング用のテンプレート  (ここから) */
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <functional>
#include <bitset>

using namespace std;
using lint = long long int;
using ll = long long int;
using lnt = long long int;
using graph = vector<vector<long long int>>;
using wgraph = vector<vector<pair<long long int, long long int>>>;
long long int INF = 1001001001001001LL;
long long int MOD = 1000000007LL;
double PI = 3.1415926535897932;
long long int di[] = {-1, 0, 1, 0, -1, 1, 1, -1};
long long int dj[] = {0, 1, 0, -1, 1, 1, -1, -1};

template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
inline void yes(){ cout << "yes" << endl; }
inline void Yes(){ cout << "Yes" << endl; }
inline void YES(){ cout << "YES" << endl; }
inline void no(){ cout << "no" << endl; }
inline void No(){ cout << "No" << endl; }
inline void NO(){ cout << "NO" << endl; }
inline void possible(){ cout << "possible" << endl; }
inline void Possible(){ cout << "Possible" << endl; }
inline void POSSIBLE(){ cout << "POSSIBLE" << endl; }
inline void impossible(){ cout << "impossible" << endl; }
inline void Impossible(){ cout << "Impossible" << endl; }
inline void IMPOSSIBLE(){ cout << "IMPOSSIBLE" << endl; }

#define rep(i,n) for(long long int i = 0; i < (n); i++)
#define rrep(i,n) for(long long int i = 1; i <= (n); i++)
#define drep(i,n) for(long long int i = (n)-1; i >= 0; i--)
#define srep(i,s,t) for(long long int i = s; i < t; i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define pb push_back

/* monkukui 競技プログラミング用のテンプレート (ここまで)*/
#define int long long

signed main(){
  
  int n, m; cin >> n >> m;
  vector<int> a(n);
  priority_queue<int> pq;
  int sum = 0;
  for(int i = 0; i < n; i++) {
    cin >> a[i];
    pq.push(a[i]);
    sum += a[i];
  }

  for(int j = 0; j < m; j++) {
    int val = pq.top();
    pq.pop();
    int to = val / 2;
    sum -= (val - to);
    pq.push(to);
  }

  cout << sum << endl;
   

  return 0;
}


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

#define rng(i, a, b) for (int i = int(a); i < int(b); i++)
#define rep(i, b) rng(i, 0, b)
#define gnr(i, a, b) for (int i = int(b) - 1; i >= int(a); i--)
#define per(i, b) gnr(i, 0, b)

using namespace std;

using ll = long long;
using P = pair<int, int>;

int main() {
  int h1, m1, h2, m2, k;
  cin >> h1 >> m1 >> h2 >> m2 >> k;
  int hm1 = 60 * h1 + m1;
  int hm2 = 60 * h2 + m2;
  int res = hm2 - hm1 - k;
  cout << res << endl;
  return 0;
}


Measured memory_bytes: 3620
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); ++i)
#define fi first
#define se second
#define INF 1000000009
#define LLINF 1000000000000000009LL
using ll = long long;

vector<int>divisor(int n){
  vector<int>d;
  for(int i=1;i*i<=n;i++){
    if(n%i==0){
      d.push_back(i);
      if(i!=n/i)d.push_back(n/i);
    }
  }
  sort(d.begin(),d.end());
  return d;
}

int main(){
  int n,k;
  cin>>n>>k;
  vector<int>a(n);
  rep(i,n)cin>>a[i];
  int sum=0;
  rep(i,n)sum+=a[i];
  vector<int>d=divisor(sum);
  int ans=1;
  for(auto x:d){
    vector<int>a_mod(n);
    rep(j,n)a_mod[j]=a[j]%x;
    sort(a_mod.rbegin(),a_mod.rend());
    int s_mod=0;
    rep(j,n)s_mod+=a_mod[j];
    int cnt=0;
    rep2(j,s_mod/x,n){
      cnt+=a_mod[j];
    }
    if(cnt<=k)ans=x;
  }
  cout<<ans<<endl;
  return(0);
}


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

int main() {
  int S1, S2, S3, D, S;
  
    cin >> S;
  	S1 = (S / 100) % 10; //1桁目
  	S2 = (S / 10) % 10; //2桁目
  	S3 = (S / 1) % 10; //3桁目
    D = S1 + S2 + S3;
    cout << D << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
using namespace std;

typedef long long ll;
typedef vector<int> vint;
typedef vector<long long> vll;
typedef pair<int,int> pint;
typedef pair<long long, long long> pll;

#define MP make_pair
#define PB push_back
#define ALL(s) (s).begin(),(s).end()
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P) 
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P) 
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P) 
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }


int N, x, y;

int G[10100];

int res;
bool seen[10100], used[10100];
void dfs(int v) {
    if (used[v]) return;
    if (seen[v]) {
        ++res;
        return;
    }
    seen[v] = true;
    int to = G[v];
    dfs(to);
    
    used[v] = true;
}


int main() {
    while (cin >> N) {
        if (N == 0) break;
        
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                cin >> x >> y;
                int to = N*x+y;
                int from = N*j+i;
                
                G[from] = to;
            }
        }
        res = 0;
        memset(seen, 0, sizeof(seen));
        memset(used, 0, sizeof(used));
        
        for (int i = 0; i < N*N; ++i) {
            if (!used[i]) dfs(i);
        }
        
        cout << res << endl;
    }
    
    return 0;
}


Measured memory_bytes: 1232
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
typedef long long LL;
int days[]={0,31,28,31,30,31,30,31,31,30,31,30,31};
bool is_uruu(int year) {
	return (year%4==0)&&(year%100!=0||year%400==0);
}
void foo(LL b,LL ka,LL t,LL w,LL ki) {
	ka+=b*20;
	t+=ka*20;
	w+=t*18;
	ki+=w*20;
	if(ki<=10) {
		printf("2012.12.%d\n",ki+21);
		return;
	}
	ki-=10;
	int year=2013;
	while(ki>0) {
		bool leap=is_uruu(year);
		if(leap) days[2]=29; else days[2]=28;
		for(int i=1;i<=12;i++) {
			if(ki>days[i]) {
				ki-=days[i];
			}else {
				printf("%d.%d.%d\n",year,i,ki);
				ki=0;
				break;
			}
		}
		year++;
	}
}
void bar(LL y,LL m,LL d) {
	LL ki=0;
	if(y==2012) {
		ki=d-21;
	}else {
		ki+=10;
		for(int i=2013;i<y;i++) {
			bool leap=is_uruu(i);
			if(leap) ki+=366; else ki+=365;
		}
		if(is_uruu(y)) days[2]=29; else days[2]=28;
		for(int i=1;i<m;i++) {
			ki+=days[i];
		}
		ki+=d;
	}
	LL w=ki/20;
	ki%=20;
	LL t=w/18;
	w%=18;
	LL ka=t/20;
	t%=20;
	LL b=ka/20;
	ka%=20;
	printf("%lld.%lld.%lld.%lld.%lld\n",b%13,ka,t,w,ki);
}
int main() {
	char S[114514];
	while(scanf("%s",S),S[0]!='#') {
		int a,b,c,d,e;
		if(sscanf(S,"%d.%d.%d.%d.%d",&a,&b,&c,&d,&e)<5) {
			sscanf(S,"%d.%d.%d",&a,&b,&c);
			bar(a,b,c);
		}else {
			foo(a,b,c,d,e);
		}

	}
}

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

int main() {
  int a,b;
  cin >> a >> b;
  int x = (a+b)/2;
  if(a%2==0&&b%2==0 || a%2==1&&b%2==1) cout << x << endl;
  else cout << x+1 << endl;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
char ai[300005];
int qw[300005];
int qe[300005];
int main()
{
    int a;
    scanf("%d",&a);
    getchar();
    scanf("%s",ai);
    long long len = strlen(ai);
    long long e=1,r=1,sum=1100000000;
    for(int i = 0;i<len;i++)
    {
        if(ai[i]=='W')
        {
            qw[i] = e;
            e++;
        }
        else
            qw[i] = e-1;
        if(ai[i]=='E')
        {
            qe[i] = r;
            r++;
        }
        else
            qe[i] = r-1;
    }
    /*for(int i=0;i<len;i++)
    {
        printf("%d %d %d\n",qw[i],qe[i],i);
    }*/
    for(int i=0;i<len;i++)
    {
        int su;
        if(ai[i]=='E'){
        su = qw[i] + qe[len-1]-qe[i];
       // printf("%d %d %d %d\n",qw[i],qe[i],i,su);
        }
        else{
        su = qw[i] + qe[len-1]-qe[i]-1;
       // printf("%d %d %d %d\n",qw[i],qe[i],i,su);
        }
        if(su<sum)
            sum =su;
    }
    printf("%lld\n",sum);
    return 0;
}
/*
8
WWWWWEEE
12
WEWEWEEEWWWE
4
5
WEEWW
*/

Measured memory_bytes: 2944
#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int H, N;
	cin >> H >> N;

	vector<int> A(N);
	int counter = 0;

	for (int i = 0; i < N; i++) 
	{
		cin >> A.at(i);
		counter += A.at(i);
	}

	if (counter < H)
	{
		cout << "No" << endl;
	}
	else 
	{
		cout << "Yes" << endl;
	}

	return 0;
}

Measured memory_bytes: 640
import java.util.*;

public class Main{
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        String a = sc.next();
        String judge = "consonant";
        if(a.equals("a") || a.equals("i") || a.equals("u") || a.equals("e") || a.equals("o")){
            judge = "vowel";
        }
        System.out.println(judge);
    }
}

Measured memory_bytes: 35740
import sys
from collections import defaultdict
finput=lambda:sys.stdin.readline().strip()

class Unionfind():
    def __init__(self,n):
        self.parents=[-1]*n
        self.ranks=[0]*n
    
    def find(self,x):
        if self.parents[x]<0:
            return x
        else:
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]
    
    def union(self,x,y):
        x=self.find(x)
        y=self.find(y)
        if x==y:
            return 
        if self.ranks[x]<self.ranks[y]:
            x,y=y,x
        self.parents[x]+=self.parents[y]
        self.parents[y]=x
        if self.ranks[x]==self.ranks[y]:
            self.ranks[x]+=1
    
    def size(self,x):
        return -self.parents[self.find(x)]
    
    def issametree(self,x,y):
        return self.find(x)==self.find(y)

def main():
    n=int(finput())
    coor=[list(map(int,finput().split()))+[i] for i in range(n)]
    coor.sort(key=lambda e:e[0])
    cost = lambda e,f:min(abs(e[0]-f[0]),abs(e[1]-f[1]))
    ew=dict(((coor[i][2],coor[i+1][2]),cost(coor[i][:2],coor[i+1][:2])) for i in range(n-1))
    coor.sort(key=lambda e:e[1])
    ew.update(dict(((coor[i][2],coor[i+1][2]),cost(coor[i][:2],coor[i+1][:2])) for i in range(n-1)))
    edges=sorted(list(iter(ew)),key=lambda e:ew[e])
    v=Unionfind(n)
    totcost=0
    # print(ew)
    # print(edges)
    for edge in edges:
        if not v.issametree(edge[0],edge[1]):
            v.union(edge[0],edge[1])
            totcost+=ew[edge]
    print(totcost)
    
if __name__=='__main__':
    main()


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

int main() {
  int x,y,a,b,c;
  cin >> x >> y >> a >> b >> c;

  vector<long> p(a);
  vector<long> q(b);
  vector<long> r(c);
  for(int i=0;i<a;i++){
    cin >> p[i];
  }
  for(int i=0;i<b;i++){
    cin >> q[i];
  }
  for(int i=0;i<c;i++){
    cin >> r[i];
  }

  //ソートをする。
  sort(p.begin(),p.end(),greater<int>() );
  sort(q.begin(),q.end(),greater<int>() );
  sort(r.begin(),r.end(),greater<int>() );

  // cout << p[0] << endl;

  long long ans=0;
  int pi = 0;
  int qi = 0;
  int ri = 0;
  bool flag=true;
  while(flag){
    if( ( (p[pi]>=q[qi] && p[pi]>=r[ri]) || (p[pi]>=r[ri] && qi>=y) )&& (pi<x && pi+qi+ri+1<=x+y)){
      ans += p[pi];
      pi++;
      // cout << "p" << ans << endl;
      continue;
    }else if( ( (q[qi]>p[pi] && q[qi]>=r[ri]) || (q[qi]>=r[ri] && pi>=x) ) && (qi <y && pi+qi+ri+1<=x+y)){
      ans += q[qi];
      qi++;
      // cout << "q" << ans << endl;
      continue;
    }else if(pi+qi+ri+1<=x+y){
      ans += r[ri];
      ri++;
      // cout << "r" << ans << endl;
      continue;
    }else{
      // cout << "out" << endl;
      break;
    }
  }

  cout << ans << endl;

}


Measured memory_bytes: 2560
import math

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

lst = [1]
K2 = 1
while K2 < K:
    K2 *= 2
    lst.append(K2)

cnt = 0
for i in range(1,N+1):
    now = math.ceil(K/i)
    if now == 1:
            cnt += lst[-1]
    else:
         for j in range(len(lst)-1):
            if lst[j] < now <= lst[j+1]:
                cnt += lst[-1] // lst[j+1]

ans = cnt / (N * lst[-1])
print(ans)


Measured memory_bytes: 3064
#include<string>
#include<string.h>
#include<map>
#include<set>
#include<vector>
#include<stdio.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
int n,k;
int main()
{
  cin>>n>>k;
  k--,n--;
  n=(n+k-1)/k;
  cout<<n<<endl;
  system("pause");
  return 0;
}

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

list_input=[]
list_uniq=[]
for i in range(N):
    a=input()
    a=int(a)
    list_input.append(a)
    
for x in list_input:
    if x not in list_uniq:
        list_uniq.append(x)
        
print(len(list_uniq))

Measured memory_bytes: 3316
#include <limits.h>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

#define int long long
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define REPS(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)
#define FOR(i, a, b) for (int i = (a), i##_len = (b); i <= i##_len; ++i)
#define REV(i, a, b) for (int i = (a); i >= (b); --i)
#define CLR(a, b) memset((a), (b), sizeof(a))
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define INF 1001001001001001001ll
#define fcout cout << fixed << setprecision(10)

using namespace std;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int N;
    cin >> N;
    vector<int> a(N), b(N);
    REP(i, N) cin >> a[i] >> b[i];

    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());

    int num = 0;
    REP(i, N) {
        int t = a[i] + num;
        if (t % b[i] == 0) continue;
        num += b[i] - (t % b[i]);
    }
    cout << num << endl;

    return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
vector<int> g[N];
bool vis[N][11];
int c[N];

struct obj {
	int u, d, c;
	obj(int a, int b, int cc) {
		u = a, d = b, c = cc;
	}
};
vector<obj> v;

void bfs(int in) {

	int u = v[in].u;
	int dis = v[in].d;
	int col = v[in].c;
	queue<pair<int, int> > q;
	if (!c[u]) c[u] = col;
	if (vis[u][dis]) return;
	q.push( { u, dis });
	vis[u][dis] = true;
	while (!q.empty()) {
		u = q.front().first;
		dis = q.front().second;
		if (!dis) break;
		q.pop();
		for (int i = 0; i < g[u].size(); i++) {
			int s = g[u][i];
			if (vis[s][dis - 1]) continue;
			vis[s][dis - 1] = true;
			q.push( { s, dis - 1 });
			if (!c[s]) c[s] = col;
		}
	}

}
int main() {

//	freopen("readin.txt", "r", stdin);

	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 0, a, b; i < m; i++) {
		scanf("%d%d", &a, &b);
		g[a].push_back(b);
		g[b].push_back(a);
	}
	int q;
	scanf("%d", &q);
	while (q--) {
		int u, d, c;
		scanf("%d%d%d", &u, &d, &c);
		v.push_back(obj(u, d, c));
	}
	reverse(v.begin(), v.end());
	for (int i = 0; i < v.size(); i++) {
		bfs(i);
	}
	for (int i = 1; i <= n; i++) {
		printf("%d\n", c[i]);
	}
	return 0;
}


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

using namespace std;
using ll = long long;

int main() {
  int n,k;
  cin >> n >> k;
  vector<ll> a(n);

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


  for (int i = k; i < n; i++) {
    if (a[i-k] < a[i]) {
      cout << "Yes" << endl;
    } else {
      cout << "No" << endl;
    }
    
  }
}


Measured memory_bytes: 4820
// #pragma GCC target("avx")  // CPU 処理並列化
// #pragma GCC optimize("O3")  // CPU 処理並列化
// #pragma GCC optimize("unroll-loops")  // 条件処理の呼び出しを減らす
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
#include<numeric>
#include<unordered_set>
#include<complex>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const double EPS=1e-10;
const double INF=1e+10;
const double PI=acos(-1.0);
const int C_SIZE = 3100000;
const int UF_SIZE = 210000;
namespace{
	long long fact[C_SIZE];
	long long finv[C_SIZE];
	long long inv[C_SIZE];
	long long Comb(int a,int b){
	 	if(a<b||b<0)return 0;
	 	return fact[a]*finv[b]%mod*finv[a-b]%mod;
	}
	void init_C(int n){
		fact[0]=finv[0]=inv[1]=1;
		for(int i=2;i<n;i++){
			inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
		}
		for(int i=1;i<n;i++){
			fact[i]=fact[i-1]*i%mod;
			finv[i]=finv[i-1]*inv[i]%mod;
		}
	}
	long long pw(long long a,long long b){
		if(a<0LL)return 0;
		if(b<0LL)return 0;
		long long ret=1;
		while(b){
			if(b%2)ret=ret*a%mod;
			a=a*a%mod;
			b/=2;
		}
		return ret;
	}
	long long pw_mod(long long a,long long b,long long M){
		if(a<0LL)return 0;
		if(b<0LL)return 0;
		long long ret=1;
		while(b){
			if(b%2)ret=ret*a%M;
			a=a*a%M;
			b/=2;
		}
		return ret;
	}
	int pw_mod_int(int a,int b,int M){
		if(a<0)return 0;
		if(b<0)return 0;
		int ret=1;
		while(b){
			if(b%2)ret=(long long)ret*a%M;
			a=(long long)a*a%M;
			b/=2;
		}
		return ret;
	}
	int ABS(int a){return max(a,-a);}
	long long ABS(long long a){return max(a,-a);}
	double ABS(double a){return max(a,-a);}
	int sig(double r) { return (r < -EPS) ? -1 : (r > +EPS) ? +1 : 0; }
	int UF[UF_SIZE];
	void init_UF(int n){
		for(int i=0;i<n;i++)UF[i]=-1;
	}
	int FIND(int a){
		if(UF[a]<0)return a;
		return UF[a]=FIND(UF[a]);
	}
	void UNION(int a,int b){
		a=FIND(a);b=FIND(b);if(a==b)return;
		if(UF[a]>UF[b])swap(a,b);
		UF[a]+=UF[b];UF[b]=a;
	}
}
// ここから編集しろ
long long p[20][20];
long long dp[1<<16];
long long ks[1<<16];
int main(){
	int a;scanf("%d",&a);
	for(int i=0;i<a;i++)for(int j=0;j<a;j++)scanf("%lld",&p[i][j]);
	for(int i=0;i<a;i++){
		for(int j=i+1;j<a;j++){
			for(int k=0;k<(1<<a);k++){
				if(k&(1<<i)){
					if(k&(1<<j)){
						ks[k]+=p[i][j];
					}
				}
			}
		}
	}
	for(int i=0;i<(1<<a);i++){
		int j=i;
		while(j){
			dp[i]=max(dp[i],dp[i-j]+ks[j]);
			j=((j-1)&i);
		}
	}
	printf("%lld\n",dp[(1<<a)-1]);
}

Measured memory_bytes: 1152
#include<bits/stdc++.h>
#define REP(i, n) for(ll i = 0; i < (ll)n; i++)
#define REPvec(itr, mp) for(auto itr = mp.begin();itr != mp.end(); itr ++)
#define all(x) x.begin(), x.end()
#define MOD 1000000007//1e9+7
using namespace std;
typedef long long unsigned int ll;
typedef vector<int >    vecint;
typedef vector<double >    vecd;
typedef vector<vector<int> >  vec2int;
typedef vector<vector<double> >  vec2d;
typedef vector<ll >     vecll;
typedef vector<string > vecstr;
typedef vector<bool > vecbool;
typedef vector<vector< bool > > vec2bool;
typedef vector<bool > vecbool;
////////////////////////////////////////////////
int main()
{
  int n, a, b; cin >> n >> a >> b;
  if((b - a)%2 == 0){
    cout << "Alice" << endl;
  }else{
    cout << "Borys" << endl;
  }
} 

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007
int modpow(int x, int k) {
  int a = 1;
  while (k) {
    if (k&1) a = (1LL*a*x) % MOD;
    x = (1LL*x*x) % MOD;
    k >>= 1;
  }
  return a;
}

int N, K;
vector<int> G;
int D[2000];
signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  cin >> N >> K;
  for (int d=1; d*d<=N; d++) {
    if (N%d) continue;
    G.pb(d);
    if (d*d != N) G.pb(N/d);
  }
  sort(all(G));
  int ans = 0;
  rep(i, G.size()) {
    int d = G[i];
    D[i] = modpow(K, (d+1)/2);
    rep(j, i) if (d%G[j] == 0) {
      D[i] = (D[i] + MOD-D[j]) % MOD;
    }
    int d2 = d;
    if (d%2 == 0) d2 /= 2;
    ans = (ans+1LL*d2*D[i]) % MOD;
  }
  cout << ans << "\n";
  return 0;
}


Measured memory_bytes: 256
n = int(input())
arr = list(map(int, input().split()))
change = 0

for i in range(n):
    minj = i
    for j in range(i, n):
        if arr[j] < arr[minj]:
            minj = j
    else:
        if i != minj:
            arr[i], arr[minj] = arr[minj], arr[i]
            change += 1

def print_space(li):
    for i in range(len(li)-1):
        print(li[i], end=' ')
    else:
        print(li[-1])

print_space(arr)
print(change)


Measured memory_bytes: 5608
import java.io.*;
import java.util.*;
import java.lang.*;
public class Main {
		
	public static void main(String[] args) {
		MyScanner sc = new MyScanner();
		String s=sc.next();
		int n=s.length();
		int c0=0;
		int c1=0;
		for(int i=0;i<n;i++) {
			if(s.charAt(i)=='0') {
				c0++;
			}else {
				c1++;
			}
		}
		
		System.out.println(2*Math.min(c0,c1));
		
	}

	
	
	
	
	
	
//----------------------------------------------------------
	static int l_min(int[] a) {
		Arrays.sort(a);
		return a[0];
	}
	static int l_max(int[] a) {
		int l=a.length;
		Arrays.sort(a);
		return a[l-1];
	}
	
	public static PrintWriter out;

	public static class MyScanner {
		BufferedReader br;
		StringTokenizer st;

		public MyScanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		long nextLong() {
			return Long.parseLong(next());
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}
			return str;
		}

	}
	

}


Measured memory_bytes: 24404
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException{

        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        int stay = Integer.parseInt(input.readLine());
        int sale = Integer.parseInt(input.readLine());
        int normalCost = Integer.parseInt(input.readLine());
        int saleCost = Integer.parseInt(input.readLine());
        if(stay > sale){
            System.out.println(sale * normalCost + (( stay - sale ) * saleCost));
        }else{
        System.out.println(stay * normalCost);
        }
    }
}


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

#define int long long

#define ii pair<int,int>
#define fi first
#define sc second

#define all(x) (x).begin(),(x).end()

signed main() {
#ifdef _DEBUG
  // freopen("in" , "r", stdin );
#endif
  ios::sync_with_stdio(0); cin.tie(0);
  int n, x;
  cin >> n >> x;
  vector<int> a(n);
  for (auto &i : a) cin >> i;
  sort(all(a));
  for (int i = 0; i < n; i++) {
    x -= a[i];
    if (x < 0 || (i == n - 1 && x != 0)) {
      cout << i << '\n';
      return 0;
    }
  }
  cout << n << '\n';
}


Measured memory_bytes: 3604
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define fi first
#define se second
#define vll vector<ll>
#define pii pair<ll,ll>
#define vvll vector< vector<ll> >
#define pb push_back
#define sz(v) (ll)(v).size()
#define inf 1e18
#define md 1000000007
#define all(v) (v).begin(),(v).end()
#define rep(i,a,b) for(ll i=a;i<b;++i)
#define tel(a){cout<<a<<"\n";}
#define tell(a,b){cout<<a<<" | "<<b<<"\n";}
#define telll(a,b,c){cout<<a<<" | "<<b<<" | "<<c<<"\n";}
#define teln(v,n){cout<<"v- ";rep(o,0,n)cout<<v[o]<<" ";cout<<"\n";}
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;

#define M 100010


int main(){
    IOS;
     
    ll n,k;cin>>n>>k;
    ll a[n];
    rep(i,0,n)cin>>a[i];
    sort(a,a+n);
    ll ans=1;
    if(a[n-1]==0 and (k&1)){
    	cout<<0;return 0;
    }
    if(a[n-1]<=0 and (k&1)){
    	for(ll i=n-1;i>=n-k;--i){a[i]%=md;(ans*=a[i])%=md,(ans+=md)%=md;}
    	cout<<ans;
    	return 0;
    }
    ll i=0,j=n-1;
    if(k&1){a[j]%=md,(ans*=a[j])%=md,(ans+=md)%=md;j--,k--;}k/=2;
	rep(p,0,k){
		ll l=a[i]*a[i+1],r=a[j]*a[j-1];
		if(l>r){l%=md;(ans*=l)%=md,(ans+=md)%=md;i+=2;}
		else {r%=md;(ans*=r)%=md,(ans+=md)%=md;j-=2;}
		// tell(i,j);
	}     
    cout<<ans;
    
    return 0;
}


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

typedef long long ll;
typedef pair<ll,ll> P;

struct BIT{
    int N;
    vector<ll> bit;
    void init(int n){
        N = n;
        bit.resize(n+1);
    }
    ll sum(int i){
        ll s = 0;
        while(i > 0){
            s += bit[i];
            i -= i & -i;
        }
        return s;
    }
    void add(int i, ll x){
        while(i <= N){
            bit[i] += x;
            i += i & -i;
        }
    }
};

int main(){
    ll n, k, ans = 0;
    cin >> n >> k;
    vector<ll> a(n+1);
    for(int i=0;i<n;i++){
        cin >> a[i+1];
        a[i+1] -= k;
        a[i+1] += a[i];
    }
    vector<P> pos(n+1);
    for(int i=0;i<=n;i++){
        pos[i] = P(a[i],i);
    }
    sort(pos.begin(), pos.end());
    BIT bit;
    bit.init(n+1);
    for(int i=0;i<=n;i++){
        int idx = pos[i].second+1;
        ans += bit.sum(idx);
        bit.add(idx,1);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 6528
#include<bits/stdc++.h>
using namespace std;
string s,s1;
int len,len1;
int main()
{
	cin>>s>>s1;
	int len=s.length();
	for(int i=0;i<len;i++)
	{
		cout<<s[i];
		if(s1[i])
		cout<<s1[i];
	}
	cout<<endl;
	return 0;
}

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

typedef long long ll;
typedef pair<ll, ll> P;


#define rep(i,n) for(ll (i)=0; (i)<(ll)(n); (i)++)
#define frep(i,m,n) for(ll (i)=(m); (i)<=(ll)(n); (i)++)
#define rrep(i,n) for(ll (i)=(n)-1; (i)>-1; (i)--)
#define frrep(i,m,n) for(ll (i)=(n); (i)>(ll)(m); (i)--)
#define ALL(x) (x).begin(), (x).end()

const ll INF = 100100100100100100;
const ll MOD = 1000000007;

// get abs
ll my_abs(ll a);
// a^n
ll a_n(ll a, ll n);
// get gcd
ll my_gcd(ll a, ll b);
// a^(-1) % MOD 
ll inv(ll a);

int main() {
    string s;
    cin >> s;
    int r=0, b=0;
    rep(i, s.size()) {
        if(s[i] == '0') r++;
        else b++;
    }
    cout << min(r,b)*2 << endl;

    return 0;
}

ll my_abs(ll a) {
    if(a >= 0) return a;
    else return -1 *a;
}

ll a_n(ll a, ll n) { 
    if(n == 0) return 1;
    
    ll ret = a, count = 1;
    while(count * 2 < n) {
        ret *= ret;
        count *= 2;
    }
    if(count == n) return ret;
    else return (ret * a_n(a, n-count));
}

ll my_gcd(ll a, ll b) {
    if(b == 0) return a;
    return my_gcd(b, a%b);
}

ll inv(ll a) {
    return a_n(a, MOD-2);
}



Measured memory_bytes: 512
#include <stdio.h>
#include <bitset>
#include <string.h>
#include <stack>
#include <algorithm>
#include <iostream>
#include <set>
#include <map>
#include <math.h>
#include <queue>
#include <complex>
#include <functional>
using namespace std ;
typedef long long ll ;
typedef long double ld ;
typedef unsigned long long ull ;
#ifdef _WIN32
#define LLD "%I64d"
#else
#define LLD "%lld"
#endif
#define pi (acos(-1.0))
#define fi first
#define se second
#define lson (o<<1),l,mid
#define rson (o<<1|1),mid+1,r
#define MP make_pair
#define sqr(x) ((x)*(x))
#define ALL(v) (v).begin(),(v).end()
#define showtime fprintf(stderr,"time = %.15f\n",clock() / (double)CLOCKS_PER_SEC)
const double eps = 1e-9 ;
const int inf = 0x3f3f3f3f ;
const ll INF = (ll)4e18 ;
const int MOD=(int)1e9+7,BAS=257,invBAS=70038911;
inline int sign(double x){return x<-eps?-1:x>eps;}
inline int clz(int x){return __builtin_clz(x);}
inline int clz(ll x){return __builtin_clzll(x);}
inline int lg2(int x){return !x ? -1 : 31-clz(x);}
inline int lg2(ll x){return !x ? -1 : 63-clz(x);}

char s[100000+10];
int main () {
	scanf ("%s", s+1);
	int n = strlen (s+1)+1;
	for (int i=1; i+1<n; i++)
		if (s[i]==s[i+1]||s[i]==s[i+2]||s[i+1]==s[i+2]) {
			printf("%d %d\n", i, i==n-2?i+1:i+2); exit(0);
		}
	puts ("-1 -1");
	return 0;
}

Measured memory_bytes: 384
from itertools import permutations, product
from math import ceil, floor

D, G = [int(elem) for elem in input().split(' ')]
point_info_list = [[int(elem) for elem in input().split()] for _ in range(D)]
assert len(point_info_list) == D
assert len(point_info_list[0]) == 2

# time complexity: O(D!)
""" min_num = float('inf')
for perm in permutations(range(D)):
    current_point = 0
    current_num = 0
    for point in perm:
        if (G - current_point) - (point + 1) * 100 * point_info_list[point][0] <= 0:
            current_num += ceil((G - current_point) / ((point + 1) * 100))
            break
        elif (G - current_point) - (point + 1) * 100 * point_info_list[point][0] - point_info_list[point][1] <= 0:
            current_num += point_info_list[point][0]
            break
        else:
            current_point += (point + 1) * 100 * point_info_list[point][0] + point_info_list[point][1]
            current_num += point_info_list[point][0]
    min_num = min(current_num, min_num)

print(min_num)
 """

# time complexity: O(D2^D)
min_num = float('inf')
for mask in product([False, True], repeat=D):
    chosen_indices = [i for i, chosen in enumerate(mask) if chosen]
    current_point = 0
    current_num_solved = 0
    for chosen_index in chosen_indices:
        point = (chosen_index + 1) * 100
        num_problems = point_info_list[chosen_index][0]
        bonus = point_info_list[chosen_index][1]
        current_point += point * num_problems + bonus
        current_num_solved += num_problems

    if current_point >= G:
        min_num = min(min_num, current_num_solved)
    else:
        chosen_indices = set(chosen_indices)
        max_index = max([i for i in range(D) if i not in chosen_indices])
        point = (max_index + 1) * 100
        num_problems = point_info_list[max_index][0]
        if current_point + point * num_problems < G:
            continue
        else:
            current_num_solved += ceil((G - current_point) / point)
            min_num = min(min_num, current_num_solved)

print(min_num)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N,M;
  cin >> N >> M;
  vector<vector<int>> RL(M,vector<int>(2));
  for (int i = 0 ; i < M ; i++) {
    cin >> RL[i][0] >> RL[i][1];
  }
  int Lm=0,Rm=N;
  for (int i = 0 ; i < M ; i++) {
    Lm = max(Lm,RL[i][0]);
    Rm = min(Rm,RL[i][1]);
  }
  cout <<(Rm-Lm+1>-1 ? Rm-Lm+1 : 0);
}

Measured memory_bytes: 5760
#include<bits/stdc++.h>
#define LLI long long int
#define ULTRA 2134567890
#define de(x) if(x!=0 && MODE==x)
#define MODE 0
#define MID 12800
using namespace std;

int A[87][87];
int B[87][87];
bool dp[87][87][MID+7];

int main()
{
    int i,j,k;
    int H,W;

    scanf("%d %d", &H, &W);
    for( i=1; i<=H; i++)
    {
        for( j=1; j<=W; j++)
        {
            scanf("%d", &A[i][j]);
        }
    }
    for( i=1; i<=H; i++)
    {
        for( j=1; j<=W; j++)
        {
            scanf("%d", &B[i][j]);
        }
    }

    dp[1][1][abs(A[1][1]-B[1][1])] = 1;
    for( i=1; i<=H; i++)
    {
        for( j=1; j<=W; j++)
        {
            for( k=0; k<=MID; k++)
            {
                if(dp[i][j][k])
                {
                    dp[i+1][j][ abs(k+A[i+1][j]-B[i+1][j]) ] = 1;
                    dp[i+1][j][ abs(k+B[i+1][j]-A[i+1][j]) ] = 1;

                    dp[i][j+1][ abs(k+A[i][j+1]-B[i][j+1]) ] = 1;
                    dp[i][j+1][ abs(k+B[i][j+1]-A[i][j+1]) ] = 1;
                }
            }
        }
    }

    int ans = 0;
    for( ans=0; !dp[H][W][ans]; ans++);
    printf("%d\n", ans);

    return 0;
}


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

const double pi  = 2 * acos(0.0);
const double eps = 1e-8;

#define REP(i,a,b) for(int i=(a); i<(b);++i)
#define rep(i,n) REP(i,0,n)
#define INF (1<<29)
#define INFLL (1L<<62)

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;

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

int main(void) {
  ios_base::sync_with_stdio(false); cin.tie(0);
  int M, Nmin, Nmax;
  while (cin >> M >> Nmin >> Nmax, M && Nmin && Nmax) {
    vector<int> P(M);
    rep(i, M) cin >> P[i];
    sort(P.begin(), P.end(), greater<int>());

    int max_gap = 0;
    int ans = 0;
    for (int n = Nmin; n <= Nmax; n++) {
      int gap = P[n-1] - P[n];
      if (gap >= max_gap) {
        max_gap = gap;
        ans = n;
      }
    }

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

Measured memory_bytes: 3116
#include <cstdio>
#define MOD 1000000007
int dp[3005][3005][2];
int main()
{
	// freopen("AGC013-D.in", "r", stdin);
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 0; i <= n; i++)
		dp[0][i][!i] = 1;
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j <= n; j++)
		{
			for (int x = 0; x < 2; x++)
			{
				if (j)
				{
					(dp[i + 1][j - 1][x | (j == 1)] += dp[i][j][x]) %= MOD;
					(dp[i + 1][j][x | (j == 1)] += dp[i][j][x]) %= MOD;
				}
				if (j != n)
				{
					(dp[i + 1][j + 1][x] += dp[i][j][x]) %= MOD;
					(dp[i + 1][j][x] += dp[i][j][x]) %= MOD;
				}
			}
		}
	}
	int ans = 0;
	for (int i = 0; i <= n; i++)
		(ans += dp[m][i][1]) %= MOD;
	printf("%d\n", ans);
	return 0;
}


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

string sum( string sa, string sb ){
    string ret = "0";
    int len = max( sa.size(), sb.size() );
    reverse( sa.begin(), sa.end() );
    reverse( sb.begin(), sb.end() );
    while( sa.size()<len )  sa += '0';
    while( sb.size()<len )  sb += '0';
    for( int i=0; i<len; i++ ){
        ret[i] += sa[i]-'0' + sb[i]-'0';
        if( ret[i] > '9' ){
            ret += '1';
            ret[i] -= 10;
        }else if( i!=len-1 ){
            ret += '0';
        }
    }
    reverse( ret.begin(), ret.end() );
    if( ret.size() > 80 ){
        ret = "overflow";
    }
    return ret;
}

int main(){
    int n;
    cin >> n;
    while(n--){
        string a, b;
        cin >> a >> b;
        cout << sum(a, b) << endl;
    }
    return 0;
}

Measured memory_bytes: 1220
#include<iostream>
#include<vector>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
using ll = long long;
using P = pair<int, int>;
#include<algorithm>
#include<math.h>
#include<map>
#include<queue>
#include<set>
 
int main() {
	int a, p;
	cin >> a >> p;
	a *= 3;
	a = a + p;
	cout << a / 2;
	return 0;
}

Measured memory_bytes: 3636
#include<iostream>
#include <iomanip>

using namespace std;
int main() 

{
  double radius, area, perimeter;
  const double PI =3.141592653589793238463;
  cin >> radius;
  area=2*radius*PI;
  perimeter=radius*radius*PI;
   cout << fixed << setprecision(6) << perimeter << " " << area << endl;
}



Measured memory_bytes: 3284
#include <algorithm>
#include <cmath>
#include <climits>
#include <cstring>
#include <cstdio>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <map> //pair is also included in this library
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

#define REP(i, s, n) for(int i = (int)(s); i < (int)(n); i++)
#define fst first
#define snd second
#define MP make_pair //incase c++11 or later is not available

using namespace std;

typedef long long int ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;

//prefer define statement
//for reason that const int ver. of INF will raise a silly warning (unused variable)
#define INF (INT_MAX/3)
#define LIM_INF (INT_MAX)
//const int INF = INT_MAX/3;
#define PI = 3.14159265358979323846
/*------------------------------------------------------------------------------*/

bool comp(PII a, PII b){
  if(a.snd > b.snd){
    return true;
  } else if(a.snd < b.snd){
    return false;
  } else if(a.fst > b.fst){
    return true;
  }
  return false;
}

int main(){
  int N;
  cin >> N;
  vector<PLL> a(N);
  VL ans = VL(N+1, 0);
  REP(i, 0, N){
    int tmp;
    cin >> tmp;
    a[i] = {i, tmp};
  }

  sort(a.begin(), a.end(), comp);

  int step = 1;
  PLL cur = a[0];

  while(step < N){
    PII next = a[step];
    ll diff = cur.snd - next.snd;
    ans[cur.fst] += diff * step;
    cur.snd -= diff;
    if(cur.fst > a[step].fst){
      cur = a[step];
    }
    step++;
  }
  ans[cur.fst] += step * cur.snd;

  REP(i, 0, N){
    cout << ans[i] << endl;
  }

  return 0;
}


Measured memory_bytes: 3456
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int A = scan.nextInt();
        int B = scan.nextInt();
        if(A>=10){
            System.out.println(B);
        }else{
            System.out.println(B+100*(10-A));
        }
    }
}


Measured memory_bytes: 24276
n,x = map(int,input().split())

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

al = [0,l[0]]
for i in range(len(l)-1):
    if i == 0:
        an = l[i] + l[i+1]
    else:
        an += l[i+1]
    al.append(an)

count = 0
for k in al:
    if k <= x:
        count += 1
            
print(count)

Measured memory_bytes: 3064
import java.util.*;

class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    ArrayList<Double> list = new ArrayList<Double>();
    while(sc.hasNext()) {
      double h = sc.nextDouble();
      list.add(h);
    }
    Double[] arr = (Double[])list.toArray(new Double[list.size()]);
    Arrays.sort(arr);
    System.out.println(arr[arr.length-1]-arr[0]);
  }
}

Measured memory_bytes: 12000
#include <stdio.h>

int main () {
	char S[5];
	scanf ("%s", S);
	int flag = 0;
	if (S[0]==S[1] && S[1]!=S[2] && S[2]==S[3])
		flag = 1;
	else if (S[0]==S[2] && S[1]==S[3] && S[0]!=S[1])
		flag = 1;
	else if (S[0]==S[3] && S[1]==S[2] && S[0]!=S[1])
		flag = 1;
	printf ("%s\n", flag?"Yes":"No");
	return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<cstdio>
#include<cstring>

namespace SaoCaoZuo
{
	typedef long long ll;
	const int N=101000,MOD=1000000007;
	inline void inc(int a,int &b){b+=a;if(b>=MOD)b-=MOD;}

	struct matrix
	{
		int s[3][3];
		matrix(int k=0)
		{
			if(!k)memset(s,0,sizeof(s));
			else if(k==1)memset(s,0,sizeof(s)),s[0][0]=s[1][1]=s[2][2]=1;
			else if(k==2)
			{
				s[0][0]=1,s[0][1]=0,s[0][2]=1;
				s[1][0]=1,s[1][1]=1,s[1][2]=1;
				s[2][0]=1,s[2][1]=2,s[2][2]=2;
			}
			else 
			{
				s[0][0]=1,s[0][1]=0,s[0][2]=0;
				s[1][0]=1,s[1][1]=1,s[1][2]=0;
				s[2][0]=1,s[2][1]=2,s[2][2]=1;
			}
		}
	};

	matrix operator * (matrix A,matrix B)
	{
		static matrix C;
		C=matrix(0);
		for(int i=0;i<3;i++)
			for(int j=0;j<3;j++)
				for(int k=0;k<3;k++)
					inc((ll)A.s[i][k]*B.s[k][j]%MOD,C.s[i][j]);
		return C;
	}
	matrix operator ^ (matrix A,int b)
	{
		static matrix C;
		C=matrix(1);
		for(;b;b>>=1,A=A*A)
			if(b&1)C=C*A;
		return C;
	}

	int n,m;
	void solve()
	{
		scanf("%d%d",&n,&m);
		matrix A(1);
		int pos=0,x,y,ans;

		for(int i=1;i<=m;i++)
		{
			scanf("%d",&x);
			y=x-pos-1;
			A=A*(matrix(2)^y);
			A=A*matrix(3);
			pos=x;
		}

//		for(int i=0;i<3;i++,printf("\n"))
//			for(int j=0;j<3;j++)printf("%d ",A.s[i][j]);
//		printf("-----------\n");

		A=A*(matrix(2)^(n-pos-1));

		ans=0;
		for(int i=0;i<3;i++)
			inc(A.s[2][i],ans);
		printf("%d\n",ans);

		/*
		ll S2=1,S1=1,S0=1;
		int ind=1;
		for(int i=1;i<n;i++)
		{
			ll fi=S2;if(s[ind]==i)fi=0,ind++;
			S2=(S2+2*S1+S0+fi)%MOD;
			S1=(S1+S0+fi)%MOD;
			S0=(S0+fi)%MOD;
		}
		printf("%lld\n",S2);
		*/
	}
}

int main()
{
	SaoCaoZuo::solve();
	return 0;
}


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

int main() {
    long long N, T;
    cin >> N >> T;

    vector<long long> t(N);
    for (int i = 0; i < N; ++i) cin >> t[i];

    long long ans = 0;
    for (int i = 0; i < N-1; ++i) {
        long long yu = T;
        long long s = t[i+1] - t[i];
        if ( s <= yu) {
            ans += s;
            yu -= s;
        } else {
            ans += T;
        }
    }
    ans += T;

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

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define all(x) (x).begin(),(x).end()

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

const int INF = 1001001001;
const vector<int> di = {-1,  0, 1, 0};
const vector<int> dj = { 0, -1, 0, 1};

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

ll GCD(ll a, ll b) {
    if (b == 0) return a;
    else return GCD(b, a % b);
}
ll LCM(ll a, ll b) { return a * b / GCD(a, b); }


int main(){
    ll N, A, B;
    cin >> N >> A >> B;

    ll block = N / (A + B);
    if (N % (A + B) == 0) {
        cout << block * A << endl;
    } else {
        ll remain = N - block *  (A + B);
        cout << block * A + min(remain, A) << endl;
    }
}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
  int N,p=0,f=1;
  scanf("%d", &N);
  int a[N];
  for(int i=0;i<N;i++) scanf("%d", &a[i]);
  while(f){
   for(int i=0;i<N;i++){
     if(a[i]%2==1){ f=0; break;}
     a[i]/=2;
   }
   if(f==1) p++;
  }
  printf("%d\n", p);
  return 0;
}

Measured memory_bytes: 128
import Control.Monad
  ( replicateM )
import Data.List
  ( sort, group )

main :: IO ()
main = do
  [n,m] <- map read . words <$> getLine
  abs   <- replicateM m $ map read . words <$> getLine 
  mapM_ print $ honsu n abs

honsu
  :: Int -> [[Int]] -> [Int]
honsu n as = map length' . group . sort . concat $ ([1..n] : as)
  where
    length' l = length l - 1

Measured memory_bytes: 1020
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define MOD 1000000007
template <typename Type>
istream &operator>>(istream &in, vector<Type> &vec) {
    ll n = vec.size();
    for (ll i = 0; i < n; i++)
        in >> vec[i];
    return in;
}
template <typename Type>
ostream &operator<<(ostream &out, vector<Type> &vec) {
    for (auto val : vec)
        out << val << " ";
    return out;
}


int main()
{
    ll n,m;
    cin>>n>>m;
    ll dp[n+1]={0};
    map<ll,ll>mark;
    for(ll i=0;i<m;i++)
    {
        ll x;
        cin>>x;
        mark[x] = 1;

    }
    dp[0]=1;
    if(mark[1]==1)
    dp[1]=0;
    else
    dp[1]=1;
    for(ll i=2;i<=n;i++)
    {
        if(mark[i]==1)
        continue;
        else
        dp[i] = (dp[i-1]+dp[i-2])%MOD;
        
    }
    cout<<dp[n]%MOD<<endl;
    return 0;
}
    


Measured memory_bytes: 7296
#include <tuple>
#include <iostream>
#include <algorithm>
using namespace std;
int T, W, H, N, a, b, c, d, dp[20][20]; tuple<int, int, int, int> Z[111];
int main() {
	cin >> T;
	while(T--) {
		cin >> W >> H >> N;
		for (int i = 0; i < N; i++) {
			cin >> a >> b >> c >> d;
			if (a > c) swap(a, c);
			if (b > d) swap(b, d);
			Z[i] = make_tuple(a, b, c, d);
		}
		sort(Z, Z + N);
		for (int i = 0; i <= H; i++) {
			for (int j = 0; j <= W; j++) {
				dp[i][j] = 0;
			}
		}
		dp[0][0] = 1;
		for (int i = 0; i <= H; i++) {
			for (int j = 0; j <= W; j++) {
				if (j) {
					tuple<int, int, int, int> v = make_tuple(j - 1, i, j, i);
					if (!binary_search(Z, Z + N, v)) dp[i][j] += dp[i][j - 1];
				}
				if (i) {
					tuple<int, int, int, int> v = make_tuple(j, i - 1, j, i);
					if (!binary_search(Z, Z + N, v)) dp[i][j] += dp[i - 1][j];
				}
			}
		}
		if (dp[H][W] == 0) cout << "Miserable Hokusai!" << endl;
		else cout << dp[H][W] << endl;
	}
	return 0;
}

Measured memory_bytes: 3044
#include <iostream>

using namespace std;

int main()
{
    int a, b, c, d;

    cin >> a >> b >> c >> d;

    if ((abs(a - b) <= d && abs(b - c) <= d) || abs(a - c) <= d)
        cout << "Yes" << endl;

    else
        cout << "No" << endl;

    return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>; 
using pll = pair<long long, long long>;
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007LL;
constexpr long long INF = 1001001001LL;
constexpr long long LINF = 1001001001001001001;
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define rept(i, j, n) for(int i=(j); i<(n); i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }


int main(){
    int k; cin >> k;
    string s = "";
    int res = -1;
    int siz = to_string(k).size();
    rep(i, siz)s += "7";
    int seven = stoi(s);

    int cnt = siz;
    rep(i, 2000000){
        int a = seven / k, b = seven % k;
        if(b==0){res = cnt; break;}
        seven = b * 10 + 7;
        cnt++;
    }
    cout << res << ln;
}
    


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

int main() {
  string s;
  cin >> s;
  int result =0;
  
  for (int i=0; i<s.size(); ++i) {
    if (s.at(i) == '+') {
      ++result;
    }
    else {
      --result;
    }
  }
  
  cout << result;
}

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

int main() {
  int n;
  cin>>n;
  vector<int> a(n);
  for(int i=0;i<n;i++){
    cin>>a.at(i);
  }
  int p=0;
  for(int i=1;i<n-1;i++){
    if(a.at(i-1)<a.at(i)&&a.at(i)<a.at(i+1)){
      p++;
    }
    else if(a.at(i-1)>a.at(i)&&a.at(i)>a.at(i+1)){
      p++;
    }
  }
  cout<<p<<endl;
}

Measured memory_bytes: 256
// {{{
#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <complex>
#include <vector>
#include <list>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <algorithm>
#include <numeric>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define FOR(i, a, b) for(ll i = static_cast<ll>(a); i < static_cast<ll>(b); i++)
#define FORR(i, a, b) for(ll i = static_cast<ll>(a); i >= static_cast<ll>(b); i--)
#define REP(i, n) for(ll i = 0ll; i < static_cast<ll>(n); i++)
#define REPR(i, n) for(ll i = static_cast<ll>(n); i >= 0ll; i--)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> IP;
typedef pair<ll, LP> LLP;

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

constexpr int INF = 100000000;
constexpr ll LINF = 10000000000000000ll;
constexpr int MOD = static_cast<int>(1e9 + 7);
constexpr double EPS = 1e-9;
// }}}

ll N, W;
ll w[101], v[101];
ll dp[101][100001];

void init()
{
}

void solve()
{
    FOR(i, 1, 100001) dp[1][i] = (i <= v[1] ? w[1] : LINF);
    FOR(i, 2, N+1){
        REP(j, 100001){
            dp[i][j] = dp[i-1][j];
            if(j-v[i] >= 0){
                dp[i][j] = min(dp[i][j], dp[i-1][j-v[i]] + w[i]);
            }
        }
    }
    REPR(i, 100000){
        if(dp[N][i] <= W){
            cout << i << endl;
            break;
        }
    }
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N >> W;
    FOR(i, 1, N+1) cin >> w[i] >> v[i];
    solve();
    return 0;
}

// vim:set foldmethod=marker:


Measured memory_bytes: 78336