akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
///Welcome to Nasif's Code
#define bug printf("bug\n");
#define bug2(var) cout<<#var<<" "<<var<<endl;
#define co(q) cout<<q<<endl;
#define all(q) (q).begin(),(q).end()
typedef long long int ll;
typedef unsigned long long int ull;
const int MOD = (int)1e9+7;
const int MAX = 1e6;
#define pi acos(-1)
#define inf 1000000000000000LL
#define FastRead    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int mat[105][105],r,c,n;
void paint1(int x)
{
    for(int i=0; i<r; i++)
    {
        for(int j=0; j<x; j++)
            mat[i][j]=1;
    }
}
void paint2(int x)
{
    for(int i=0; i<r; i++)
    {
        for(int j=x; j<c; j++)
            mat[i][j]=1;
    }
}
void paint3(int y)
{
    for(int i=0; i<c; i++)
    {
        for(int j=0; j<y; j++)
            mat[j][i]=1;
    }
}
void paint4(int y)
{
    for(int i=0; i<c; i++)
    {
        for(int j=y; j<r; j++)
            mat[j][i]=1;
    }
}
int main()
{
    FastRead
    //freopen("output.txt", "w", stdout);
    cin>>c>>r>>n;
    for(int i=0; i<n; i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        if(z==1)
            paint1(x);
        else if(z==2)
            paint2(x);
        else if(z==3)
            paint3(y);
        else
            paint4(y);
    }
    int cnt=0;
    for(int i=0; i<r; i++)
        for(int j=0; j<c; j++)
            if(!mat[i][j])
                cnt++;
    cout<<cnt<<endl;

    return 0;
}


Measured memory_bytes: 3668
import java.util.*;
public class Main
{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		double D = sc.nextDouble();
		int count=0;
		for(int i=0;i<N;i++){
		    double x = sc.nextDouble();
		    double y = sc.nextDouble();
		    if(D>=Math.sqrt(x*x +y*y)){
		        count++;
		    }
		}
		System.out.println(count);
	}
}


Measured memory_bytes: 64384
function main()
	H,W=map(x->parse(Int,x),split(readline()))
	S=String[]
	for _=1:H
		push!(S,chomp(readline()))
	end
	vis=zeros(Int,H,W)
	ans=0
	for i=1:H,j=1:W
		if vis[i,j]==1
			continue
		end
		P=Pair{Int,Int}[i=>j]
		b=w=0
		vis[i,j]=1
		while !isempty(P)
			x,y=shift!(P)
			if S[x][y]=='#'
				b+=1
			else
				w+=1
			end
			for (tx,ty)=[x-1=>y,x+1=>y,x=>y-1,x=>y+1]
				if 1<=tx<=H&&1<=ty<=W&&S[tx][ty]!=S[x][y]&&vis[tx,ty]==0
					vis[tx,ty]=1
					push!(P,tx=>ty)
				end
			end
		end
		ans+=b*w
	end
	println(ans)
end
main()


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



int main(){
	int N;
	cin>>N;
	int a[N];
	for(int i=0;i<N;i++){
		cin>>a[i];
	}
	long long dp[N][N]; //dp[i][j] i番目の要素からj+1個における最小値
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
			if(j==0)dp[i][j]=0;
			else dp[i][j]=99999999999999999;
		}
	}
	
	for(int i=1;i<N;i++){
		for(int j=0;j<N-i;j++){
			for(int x=0;x<i;x++){
				dp[j][i]=min(dp[j][i],dp[j][x]+dp[j+x+1][i-x-1]);
			}
			for(int x=0;x<i+1;x++){
				int y = j+x;
				dp[j][i]+=a[y];
			}
		}
	}
	
	cout<<dp[0][N-1]<<endl;
	
	return 0;
}

Measured memory_bytes: 1536
#include <cstring>
#include <queue>
#include <iostream>
typedef long long ll;

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

#include <cstdio>
inline int getInt(){ int s; scanf("%d", &s); return s; }

#include <set>
using namespace std;

int main(){
  const int n = getInt();
  const int k = getInt();
  vector<int> a(n);
  REP(i,n) a[i] = getInt();

  vector<vector<int> > dp(n + 1, vector<int>(k + 1));
  dp[0][k] = 1;
  const ll mod = 1000000007;
  REP(i,n){
    ll sum = 0;
    for(int j = k; j >= 0; j--){
      sum += dp[i][j];
      if(j + a[i] + 1 <= k){
	sum += mod - dp[i][j + a[i] + 1];
      }
      sum %= mod;
      dp[i + 1][j] = sum;
    }
  }

  printf("%d\n", dp[n][0]);
}

Measured memory_bytes: 40192
#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>
#define popcount __builtin_popcount
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll MOD=1e9+7;
ll powmod(ll a, ll k){
    ll ap=a, ans=1;
    while(k){
        if(k&1){
            ans*=ap;
            ans%=MOD;
        }
        ap=ap*ap;
        ap%=MOD;
        k>>=1;
    }
    return ans;
}
ll inv(ll a){
	return powmod(a, MOD-2);
}
ll f[1500001], invf[1500001];
void fac(int n){
    f[0]=1;
    for(ll i=1; i<=n; i++) f[i]=f[i-1]*i%MOD;
    invf[n]=inv(f[n]);
    for(ll i=n-1; i>=0; i--) invf[i]=invf[i+1]*(i+1)%MOD;
}
ll comb(int x, int y){
    if(x<y) return 0;
    return f[x]*invf[y]%MOD*invf[x-y]%MOD;
}
int main()
{
    ll n, m, k; cin>>n>>m>>k;
    ll s1=0, s2=0;
    for(ll i=1; i<n; i++){
        s1+=i*(n-i);
    }
    for(ll i=1; i<m; i++){
        s2+=i*(m-i);
    }
    ll c=1;
    for(ll i=1; i<=k-2; i++){
        c*=((n*m-1-i)%MOD);
        c%=MOD;
        c*=inv(i);
        c%=MOD;
    }
    ll ans=m*m%MOD*s1%MOD+n*n%MOD*s2%MOD;
    ans*=c;
    ans%=MOD;
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] X = new int[N];
		boolean ok = true;
		if(N % 2 == 1) {
			for(int i = 0; i < N; i++) {
				int A = sc.nextInt();
				if(A % 2 == 1) {
					ok = false;
					break;
				}
				X[A]++;
				if(X[A] > 2 || X[0] > 1) {
					ok = false;
					break;
				}
			}		
		}
		else {
			for(int i = 0; i < N; i++) {
				int A = sc.nextInt();
				if(A % 2 == 0) {
					ok = false;
					break;
				}
				X[A]++;
				if(X[A] > 2) {
					ok = false;
					break;
				}
			}		
		}
		long ans = 1;
		for(int i = 0; i < N/2; i++)
			ans = ans * 2 % 1000000007;
		System.out.println(ok ? ans : 0);
	}

}

Measured memory_bytes: 50312
#include <stdio.h>
#define N 110

void sort(int data[], int left, int right)
{
	int sample = data[left], lptr = left, rptr = right;
	if (lptr < rptr){
		while (lptr != rptr){
			while ((sample < data[rptr]) && (lptr != rptr)) rptr--;
			if (lptr != rptr) data[lptr++] = data[rptr];
			while ((data[lptr] < sample) && (lptr != rptr)) lptr++;
			if (lptr != rptr) data[rptr--] = data[lptr];
		}
		data[lptr] = sample;
		sort(data, left, lptr - 1);
		sort(data, rptr + 1, right);
	}
}
int count(int data[], int n)
{
	int i, cnt = 1;
	for (i = 1; i < n; i++) {
		if (data[i] != data[i - 1]) cnt++;
	}
	return cnt;
}
int main(void)
{
	int n;
	int d[N];
	scanf("%d", &n);
	for (int i = 0; i < n; i++) scanf("%d", &d[i]);
	sort(d, 0, n - 1);
	printf("%d\n", count(d, n));
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define fast() ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int main(){
    fast();
    int x ;
    cin >> x ;
    if(x == 0)
        cout << 1 << endl;
    else
        cout << 0 << endl;
    return 0;
}


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

int main(){
  int H, W;
  cin >> H >> W;
  
  for(int i=0; i<(W+2); i++)
    cout << "#";
  cout << endl;
  
  for(int i=0; i<H ;i++){
    vector<string> vec(H);
    cin >> vec.at(i);
    cout << "#" << vec.at(i) << "#" <<endl;
  }
  
  for(int i=0; i<(W+2); i++)
    cout << "#";
  
}
  
  

Measured memory_bytes: 256
n,m=map(int,input().split())
uv=[list(map(int, input().split())) for _ in range(m)]
s,t=map(int,input().split())

graph = [[] for _ in range(n)]
for v in uv:
    graph[v[0]-1].append(v[1]-1)
# print(graph)
s-=1
t-=1

is_checked=[[0]*3 for _ in range(n)]
is_checked[s][0]=1

ans=-1

from collections import deque
q=deque()
q.append([s,0])

while q:
    v, cnt=q.popleft()
    if v==t and cnt%3==0:
        ans=cnt//3
        break
    for i in graph[v]:
        if is_checked[i][(cnt+1)%3]==0:
            q.append([i, cnt+1])
            is_checked[i][(cnt+1)%3]=1
# print(is_checked)
print(ans)



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

int main() {
  long n;
  cin >> n;
  long long a[n];
  for (long i = 0; i < n; i++) {
    cin >> a[i];
    if (a[i] == 0) {
      cout << 0;
      return 0;
    }
  }
  
  long long result = 1;
  for (long i = 0; i < n; i++) {
    if (a[i] > 1000000000000000000/result) {
      result = -1;
      break;
    }
    result *= a[i];
  }
  
  cout << result;
  
  return 0;
}

Measured memory_bytes: 4300
#include <algorithm>
#include <iostream>
#define N 20000
#define M 256
#define INF (1e9)
using namespace std;
int n,m,c[N],x[N],y,d[N][M],ans;

int main(){
  
  while(1){
    cin>>n>>m;
    if(!n&&!m) break;
    for(int i=0;i<m;i++) cin>>c[i];
    for(int i=0;i<n;i++) cin>>x[i];
    for(int i=0;i<n;i++)
      for(int j=0;j<M;j++) d[i][j]=INF;
    y=128;
    for(int i=0;i<m;i++){
      int next=y+c[i];
      if(next>255) next=255;
      if(next<0) next=0;
      d[0][next]=(x[0]-(next))*(x[0]-(next));
    }
    for(int i=0;i<n-1;i++){
      for(int j=0;j<M;j++){
	if(d[i][j]==INF) continue;
	for(int k=0;k<m;k++){
	  int next=j+c[k];
	  if(next>255) next=255;
	  if(next<0) next=0;
	  d[i+1][next]=min(d[i+1][next],d[i][j]+(x[i+1]-(next))*(x[i+1]-(next)));
	}
      }
    }
    ans=INF;
    for(int i=0;i<M;i++) ans=min(ans,d[n-1][i]);
    cout<<ans<<endl;
  }
  return 0;
}

Measured memory_bytes: 21240
#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;
static const double eps = 1e-10;

class Point
{
public:
	double x, y;
	Point(double x = 0, double y = 0) : x(x), y(y){}

	Point operator + (Point p){ return(Point(x + p.x, y + p.y)); }
	Point operator - (Point p){ return(Point(x - p.x, y - p.y)); }
	Point operator * (double a){ return(Point(a * x, a * y)); }
	Point operator / (double a){ return(Point(x / a, y / a)); }

	double abs(){ return(sqrt(norm())); }
	double norm(){ return(x * x + y * y); }

	bool operator < (const Point& p) const
	{
		return(x != p.x ? x < p.x : y < p.y);
	}

	bool operator == (const Point& p) const
	{
		return(fabs(x - p.x) < eps && fabs(y - p.y) < eps);
	}
};
typedef Point Vector;

struct Segment
{
	Point p1, p2;
};
typedef Segment Line;

class Circle
{
public:
	Point c;
	double r;
	Circle(Point c = Point(), double r = 0.0): c(c), r(r){}
};

double dot(Vector a, Vector b)
{
	return(a.x * b.x + a.y * b.y);
}

double cross(Vector a, Vector b)
{
	return(a.x * b.y - a.y * b.x);
}

Point project(Segment s, Point p)
{
	Vector base = s.p2 - s.p1;
	double r = dot(p - s.p1, base) / base.norm();
	return(s.p1 + base * r);
}

void solve()
{
	Segment s;
	cin >> s.p1.x >> s.p1.y >> s.p2.x >> s.p2.y;
	int q;
	cin >> q;
	for (int i = 0; i < q; ++i)
	{
		Point p;
		cin >> p.x >> p.y;
		Point res = project(s, p);
		printf("%.10f %.10f\n", res.x, res.y);
	}
}

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

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

typedef long long ll;
typedef pair<int,int> ii;
typedef tree<ii,null_type,less<ii>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	ll H,W; cin>>H>>W;
	if(H==1||W==1) cout<<1<<"\n";
	else cout<<(H*W+1)/2<<"\n";
	return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef long double ld;
ll n, m;
//ld ;
//string s;

int main() {
    cin >> n >> m;
    ll x[n];
    for(ll i0=0;i0<n;i0++){
        x[i0] = 10;
    }
    ll ans = 0;
    for(ll i1=0; i1<m;i1++){
        ll s;
        ll c;
        cin >> s >> c;
        if(x[s-1]==10){
            x[s-1] = c; 
        }else if(x[s-1]!=c){
            ans = -1;
        }
    }
    if(n>1&&x[0]==0) ans=-1;
    if(ans!=-1){
        for(ll i2=0;i2<n;i2++){
            if(x[i2]==10){
                x[i2]=(i2!=0)?0:(m==0&&n==1)?0:1;
            }
            ans += (x[i2]*pow(10,n-1-i2));
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>

typedef struct{
  int parent;
  int left;
  int right;
}tree;

tree *TREE;

int N;

#define fr -1

void JUDGE(int);


int main(){
  int id,l,child,i,j,degree;

  scanf("%d",&N);
  TREE = (tree *)malloc(sizeof(tree)*N);
  
  for(i=0;i<N;i++){
    TREE[i].parent = fr;
    TREE[i].left = fr;
    TREE[i].right = fr;
  }
  
  for(i=0;i<N;i++){
    scanf("%d%d",&id,&degree);
  
  for(j=0;j<degree;j++){
    l = child;
    scanf("%d",&child);
    TREE[child].parent = id;

    if(j==0){
      TREE[id].left = child;
    }
    else if(j>0){
      TREE[l].right = child;
    }
  }
  }

  for(i=0;i<N;i++){
    JUDGE(i);
  }
  return 0;
}

void JUDGE(int n){
  int i = TREE[n].parent;
  int depth = 0;
  while(i!=fr){
    i = TREE[i].parent;
    depth++;
  }
  
  printf("node %d: parent = %d, depth = %d,",n,TREE[n].parent,depth);
  if(depth == 0){
    printf(" root, [");
  }
  else if(TREE[n].left == fr){
    printf(" leaf, [");
  }
  else printf(" internal node, [");

  i=TREE[n].left;
  while(i!=fr){
    printf("%d",i);

    i = TREE[i].right;

    if(i!=fr){
      printf(", ");
    }
  }
  printf("]\n");
}

Measured memory_bytes: 1784
#include <bits/stdc++.h>
#include <string>
using namespace std;
 
int main() {
  int a,b;
  cin >> a >> b;
  int N = a*pow(10,int(log10(b))+1)+b;
  if( sqrt(N) == int(sqrt(N)) ){
      cout << "Yes" << endl;
  }else{
  cout << "No" << endl;
}
    }

Measured memory_bytes: 512
'use strict'

const main = input => {
	const args = input.split('\n').map(arg => arg.split(' '))
	const n = parseInt(args[0][0], 10)
	const d = parseInt(args[0][1], 10)

	console.log( Math.ceil(n / (d * 2 + 1)) )
}

main(require('fs').readFileSync('/dev/stdin', 'utf8'))


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

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	int n; cin>>n;
	vector<int>h(n),cnt(n,0); for(auto&i:h)cin>>i;
	int ans=0;
	for(int i=0;h!=cnt;i=0){
		int w=100;
		while(i<n&&h.at(i)==0)++i;
		int j=i+1;
		while(j<n&&h.at(j)!=0)++j;
		for(int k=i;k<j;++k)w=min(w,h.at(k));
		for(int k=i;k<j;++k)h.at(k)-=w;
		ans+=w;
	}
	cout<<ans<<"\n"s;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize ("Ofast")
#pragma GCC optimization ("unroll-loops, no-stack-protector")
#pragma GCC target ("avx")
#pragma GCC target ("avx2")
#pragma GCC target ("fma")
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ll long long
#define ull unsigned long long
#define ld long double
#define pii pair <int, int>
#define pll pair <ll, ll>
#define pci pair <char, int>
#define pld pair <ld, ld>
#define ppld pair <pld, pld>
#define ppll pair <pll, pll>
#define pldl pair <ld, ll>
#define vll vector <ll>
#define vvll vector <vll>
#define vpll vector <pll>
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define mll map <ll, ll>
#define fastmap gp_hash_table
#define cd complex <double>
#define vcd vector <cd>
#define PI 3.14159265358979
#define ordered_set tree <ll, null_type, less <ll>, rb_tree_tag, tree_order_statistics_node_update>
#pragma 03
using namespace std;
using namespace __gnu_pbds;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int main(){
	fastio;
	string s, t; cin >> s >> t;
	ll fans = 1e18;
	for (ll i = 0; i <= s.length() - t.length(); i++){
		ll ans = 0;
		for (ll j = 0; j < t.length(); j++) ans += (t[j] != s[i + j]);
		fans = min(fans, ans);
	}
	cout << fans << endl;
}

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

int main() {
  int N, K, x, sum = 0;
  cin >> N >> K;
  for (int i = 0; i < N; i++) {
    cin >> x;
    if (x > K - x) sum += 2 * (K - x);
    else sum +=  2 * x;
  }
  cout << sum << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
 
int main()
{
  int i,r,x;
  char moji[100];
  scanf("%s", moji);
  for(i=0; moji[i]!='\0'; ++i);
  for(r=0;r<i;r++){
  	 printf("x");
  }
  return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
#define int long long 
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)

using namespace std ;

int n , m , c , cnt =0 , temp ;
int b[50] , a[50][50];

int32_t main(){IOS;

        cin >> n >> m >> c ; 
        for(int i=0;i<m;i++) cin >> b[i];
        for(int i=0;i<n;i++)
                for(int j=0;j<m;j++)
                        cin>>a[i][j];
        for(int i=0;i<n;i++){
                temp = c ;
                for(int j=0;j<m;j++)
                        temp += a[i][j]*b[j];
                if(temp>0) cnt++;
        }

        cout << cnt << endl ;

        return 0;
}


Measured memory_bytes: 256
/*  ex9_1
    shu_t */

#include <stdio.h>
#include <stdlib.h>
//1<=|s|<=10 + '\0'
#define SIZE 11

typedef struct stack{
    int size;//max size of stack
    int count;//the number of data
    char data[SIZE];//data array
    char *top;//pointer of top
}stack;

void initialize_stack(stack *stk){//initialization
    stk->count=0;
    stk->size = SIZE;
    stk->top=&(stk->data[SIZE]);//top is final element
}

void push(stack *stk,char elem){
	if(stk->count < stk->size){//prevent overflow
        stk->top--;//push top
        *(stk->top)=elem;//store data
        stk->count++;//increment
    }
}

void pop(stack *stk){
    if(stk->count > 0){//prevent underflow
        stk->top++;//pop top
        stk->count--;//decrement
    }
}

void print_stack(stack *stk){
    char *ptr;
    int i;
    ptr = stk->top;//to top pointer
    while(i<stk->count-1){//move to old data
        ptr++;
        i++;
    }
    for(i=0;i<stk->count;i++){//from old data to new data
        printf("%c",*ptr--);
    }
    printf("\n");//make a new line
}

int main(void){
    stack string;
    int i;//roop variable
    char keyboard[SIZE];//for input
    
    //input string
    scanf("%s",keyboard);
    //initialize stack
    initialize_stack(&string);
    //stack
    for(i=0;i<SIZE;i++){
        if(keyboard[i] == '0'){
            push(&string,'0');
        }
        else if(keyboard[i] == '1'){
            push(&string,'1');
        }
        else if(keyboard[i]=='B'){
            pop(&string);
        }
    }
    //output
    print_stack(&string);
    return 0;
}

Measured memory_bytes: 1632
#include <iostream>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <cstdio>

using namespace std;

int main(){
    map<string, set<int>> m;
    string s; int t;
    char c;
    while(cin>>t, getchar(), cin>>s){
        m[s].insert(t);
    }
    for(string i:{"A", "B", "AB", "O"}){
        cout << m[i].size() << endl;
    }
}

Measured memory_bytes: 1212
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Main m = new Main();
		m.run();
	}

	Scanner sc = new Scanner(System.in);

	void run() {
		int n = sc.nextInt();
		int a = sc.nextInt();
		int b = sc.nextInt();
		
		if(a+b > n + 1){
			System.out.println(-1);
			return;
		}
		
		if((long)a*b < n){
			System.out.println(-1);
			return;
		}
		
		
		x(a,b,n);		
		
		
	}

	void x(int a, int b, int n) {

		int z = n;
		int[] res = new int[n];
		for (int ind = 0;ind < n;) {
			int x = (int)Math.min((long)a * (b-1) + 1, z);
			for (int y = x; y <= z; y++) {
				res[ind] = y;
				ind++;
			}
			b--;
			z = x-1;
		}
		for(int i =0  ; i < n-1 ; i ++){
			System.out.print(res[i] + " ");
		}
		System.out.println(res[n-1]);
			
	}

}


Measured memory_bytes: 51064
#include<bits/stdc++.h> //ABC 163_d
#define ll long long
using namespace std;
ll n,ans,k;
const ll mod=1e9+7;
int main(){
	cin>>n>>k;
	for(ll i=k;i<=n+1;i++){
		ll l=(0+i-1)*i/2;
		ll r=(n-i+1+n)*i/2;
		ans=(ans+r-l+1)%mod;
	}
	cout<<ans;
	return 0;
}

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


signed main(){
    //cout << setprecision(16) ;
    ios::sync_with_stdio(false);
	cin.tie(0);

    string s;
    cin>>s;
    string pre ="", now="";
    pre += s[0];
    ll cnt=1;
    
    for(int i=1;i<s.size();i++){
        now += s[i];
        if(pre!=now){
            //cerr<<pre<<" "<<now<<endl;
            pre = now;
            now = "";
            cnt++;
        }
    }
    
    cout<<cnt<<endl;
}

Measured memory_bytes: 720
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse2")

    /*
    ||||||||||||||||||||||||||||||||||||||||||||||||
       |      |||         |      ||||    ||||  |   |
      | |     |   |      | |     |   |  |      |   |
     |   |    |    |    |   |    |   |  |      |   |
    |||||||   |    |   |||||||   |||     |||   |||||
    |     |   |   |    |     |   | |        |  |   |
    |     |   |||      |     |   |  ||  ||||   |   |
    ||||||||||||||||||||||||||||||||||||||||||||||||

    */
    using namespace std;
    //#include "testlib.h"
    #define ff first
    #define ss second
    #define mp make_pair
    #define all(v) v.begin(),v.end()
    #define int long long
    #define ll long long
    #define M 1000000007
    #define inputarr(a,n) for(int i=0;i<n;++i) cin>>a[i]
    #define GCD(m,n) __gcd(m,n)
    #define LCM(m,n) m*(n/GCD(m,n))
    #define mii  map<ll ,ll >
    #define msi  map<string,ll >
    #define mis  map<ll int, string>
    #define rep(a,b)    for(ll i=a;i<b;i++)
    #define rep0(n)    for(ll i=0;i<n;i++)
    #define repi(i,a,b) for(ll i=a;i<b;i++)
    #define pb push_back
    #define vi vector<ll>
    #define mp make_pair
    #define vs vector<string>
    #define ppb pop_back
    #define endl '\n'
    #define asdf ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    #define r0 return 0;
    #define FORD(i, a, b) for (int i = (int) (a); i >= (int) (b); --i)
    #define FORE(it, c) for (__typeof((c).begin()) it = (c).begin(); it != (c).end(); ++it)
    #define inputoutput freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
    #define input freopen("input.txt", "r", stdin);
    #define Set(a, s) 4(a, s, sizeof (a))
    #define FOR repi
    #define pii pair<int,int>
    #define REVERSE(v) reverse(ALL(v))
    #define display(x) trav(a,x) cout<<a<<" ";cout<<endl
    #define debug cerr<<"bhau"<<endl
    #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
    template <typename Arg1>
    void __f(const char* name, Arg1&& arg1){
        std::cerr << name << " : " << arg1 << endl;
    }
    template <typename Arg1, typename... Args>
    void __f(const char* names, Arg1&& arg1, Args&&... args){
        const char* comma = strchr(names + 1, ',');std::cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
    }
 
    //#define float long double
    ll max(ll a, ll b) { return (a > b)? a : b;}
    int min(int a, int b) { return (a < b)? a : b;}


     int solve()
     {  
        string s;int a;cin>>a>>s;
        if(a<3200) cout<<"red";
            else cout<<s;

        r0   
     }
    signed main()
    {   
        asdf
        
        int t=1;
        //cin>>t;
        while(t--)
        {
            solve();
        }     
        
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define FastRead ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long int
#define ld long double
#define FOR(i,a,n) for (int i=(a);i<=(n);++i)
#define RFOR(i,a,n) for (int i=(n);i>=(a);--i)
#define FI(i,n) for (int i=0; i<(n); ++i)
#define ZERO(a) memset((a),0,sizeof((a)))
#define f first
#define s second
#define pb push_back
#define mk make_pair
#define all(g) g.begin(),g.end()
int fastMax(int x, int y) { return (((y-x)>>(32-1))&(x^y))^y; }
int fastMin(int x, int y) { return (((y-x)>>(32-1))&(x^y))^x; }

// #include <ext/pb_ds/assoc_container.hpp> // Common file
// #include <ext/pb_ds/tree_policy.hpp>     // Including tree_order_statistics_node_updat
// using namespace __gnu_pbds;
// typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

// I am questioning life and universe and 
// everything else after looking at this

const ll MAXN = 2e5 + 10;
ll a[MAXN];
// ll seg[4*MAXN];

// void build(ll node,ll s,ll e){
//     if(s > e) return;
//     if(s == e){
//         seg[s] = a[s];
//         return;
//     }

//     ll mid = (s+e)>>1;
//     build(2*node,s,mid);
//     build(2*node+1,mid+1,e);

//     seg[node] = __gcd(seg[2*node],seg[2*node+1]);
// }

// ll x = 1;

// ll query(ll node,ll s,ll e,ll qs,ll qe){
//     if(s > e || qs > e || qe < s) return x; 

//     if(qs <= s && e <= qe){
//         return seg[node];
//     }

//     ll mid = (s+e)>>1;
//     return __gcd(query(2*node,s,mid,qs,qe),query(2*node+1,mid+1,qs,qe));
// }


ll prefix[MAXN],suffix[MAXN];
void solve(){
    ll n; cin>>n;

    
    FOR(i,1,n){
        cin>>a[i];
        if(i == 1)
            suffix[i] = a[i];
        else suffix[i] = __gcd(suffix[i-1],a[i]);
    }

    RFOR(i,1,n){
        if(i == n) prefix[i] = a[i];
        else prefix[i] = __gcd(prefix[i+1],a[i]);
    }

    ll ans = 1;
    FOR(i,1,n){
        if(i == 1) ans = max(ans,prefix[i+1]);
        else if(i == n) ans = max(ans,suffix[i-1]);
        else ans = max(ans,__gcd(prefix[i+1],suffix[i-1]));
    }

    cout<<ans<<endl;
}   

signed main(){
 
    FastRead;    

    ll t;
    t = 1; 
    // cin>>t;
    while(t--) solve();
    
}

Measured memory_bytes: 3584
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
using in = int64_t;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
const double PI=3.14159265358979323846;
const in MOD = 1000000007;
const in INF=1<<30;
using P=pair<int,int>;
vector<int> dx={0,1,-1,0};
vector<int> dy={1,0,0,-1};

map<int,int> soin(int n){
    map<int,int> ret;
    for(int i=2;i*i<=n;i ++){
        while(n%i==0){
            ret[i] ++;
            n /= i;
        }
    }
    if(n!=1) ret[n]=1;
    return ret;
}

int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cout << fixed << setprecision(10);
    int n;
    cin>>n;
    cout<<n<<":";
    auto x=soin(n);
    for(auto y: x){
        rep(i,y.second) cout<<" "<<y.first;
    }
    cout<<endl;
}


Measured memory_bytes: 3216
def get_input():
    while True:
        try:
            yield ''.join(raw_input())
        except EOFError:
            break

for a in list(get_input()):
	a = float(a)
	sum = 0

	for i in range(10):
		sum += a
		a = a * 2 if i % 2 == 0 else a / 3

	print sum

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

int main(){
  int N,M;
  cin >> N >> M;
  vector<set<int>> Fri(N);
  for(int i=0;i<M;i++){
    int a,b;
    cin >> a >> b;
    --a;
    --b;
    Fri[a].insert(b);
    Fri[b].insert(a);
  }
  vector<bool> seen(N,false);
  int ans=0;
  for(int i=0;i<N;i++){
    if(seen[i]){
      continue;
    }
    int count=1;
    stack<int> stack;
    stack.push(i);
    seen[i]=true;
    while(!stack.empty()){
      int state=stack.top();
      stack.pop();
      for(int x:Fri[state]){
        if(seen[x]){
          continue;
        }
        stack.push(x);
        seen[x]=true;
        count++;
      }
    }
    ans=max(ans,count);
  }
  cout << ans << endl;
}

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

using namespace std;

int main()
{
    int N,sum=0;
    long long x,y,len,D;
    cin>>N>>D;
    while(N--)
    {
        scanf("%lld %lld",&x,&y);
        len=x*x+y*y;
        if(len<=D*D)
            sum++;
    }
    cout<<sum<<endl;
    return 0;
}


Measured memory_bytes: 3760
require 'prime'
def main
  n = gets.chomp.to_i
  list = n.times.map{ gets.chomp.to_i }
  solve(list)
end

def solve(list)
  c = 1
  list.each do |n|
    c = c.lcm(n)
  end
  puts c
end

main if $0 == __FILE__

Measured memory_bytes: 3964
const int LG = 21;
const int FN = 400005;
const long long MOD = 1e9 + 7;
const long long INF = 1e9;
const long long INFLL = 1e18;

#include <bits/stdc++.h>

using namespace std;

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

#define forn(i, n) for (int (i) = 0; (i) != (n); (i)++)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define popcount(x) __builtin_popcount(x)
#define popcountll(x) __builtin_popcountll(x)
#define fi first
#define se second
#define re return
#define pb push_back
#define uniq(x) sort(all(x)); (x).resize(unique(all(x)) - (x).begin())

#ifdef LOCAL
#define dbg(x) cerr << __LINE__ << " " << #x << " " << x << endl
#define ln cerr << __LINE__ << endl
#else
#define dbg(x) void(0)
#define ln void(0)
#endif // LOCAL

int cx[4] = {-1, 0, 1, 0};
int cy[4] = {0, -1, 0, 1};
string Ans[2] = {"No", "Yes"};
string ANS[2] = {"NO", "YES"};

ll inq(ll x, ll y)
{
    if (!y) re 1 % MOD;
    ll l = inq(x, y / 2);
    if (y % 2) re l * l % MOD * x % MOD;
    re l * l % MOD;
}

ll rev(ll x)
{
    return inq(x, MOD - 2);
}

bool __precomputed_combinatorics = 0;
vector<ll> __fact, __ufact, __rev;

void __precompute_combinatorics()
{
    __precomputed_combinatorics = 1;
    __fact.resize(FN);
    __ufact.resize(FN);
    __rev.resize(FN);
    __rev[1] = 1;
    for (int i = 2; i < FN; i++) __rev[i] = MOD - __rev[MOD % i] * (MOD / i) % MOD;
    __fact[0] = 1, __ufact[0] = 1;
    for (int i = 1; i < FN; i++) __fact[i] = __fact[i - 1] * i % MOD, __ufact[i] = __ufact[i - 1] * __rev[i] % MOD;
}

ll fact(int x)
{
    if (!__precomputed_combinatorics) __precompute_combinatorics();
    return __fact[x];
}

ll cnk(int n, int k)
{
    if (k < 0 || k > n) return 0;
    if (!__precomputed_combinatorics) __precompute_combinatorics();
    return __fact[n] * __ufact[n - k] % MOD * __ufact[k] % MOD;
}

int Root(int x, vector<int> &root)
{
    if (x == root[x]) return x;
    return root[x] = Root(root[x], root);
}

void Merge(int v, int u, vector<int> &root, vector<int> &sz)
{
    v = Root(v, root), u = Root(u, root);
    if (v == u) return;
    if (sz[v] < sz[u])
    {
        sz[u] += sz[v];
        root[v] = u;
    }
    else
    {
        sz[v] += sz[u];
        root[u] = v;
    }
}

int ok(int x, int n)
{
    return 0 <= x && x < n;
}

void bfs(int v, vi &dist, vector<vi> &graph)
{
    fill(all(dist), -1);
    dist[v] = 0;
    vi q = {v};
    for (int i = 0; i < q.size(); i++)
    {
        for (auto u : graph[q[i]])
        {
            if (dist[u] == -1)
            {
                dist[u] = dist[q[i]] + 1;
                q.push_back(u);
            }
        }
    }
}


signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    if (n <= 999) cout << "ABC";
    else cout << "ABD";
}

/* Note:
Check constants at the beginning of the code.
    N is set to 4e5 but be careful in problems with large constant factor.
    Setting N in every problem is more effective.
Check corner cases.
    N = 1
No def int long long for now.
Add something here.
*/


Measured memory_bytes: 256
H, W = list(map(int, input().split()))
S = [input() for _ in range(H)]
field = [[0 for w in range(W+2)] for h in range(H+2)]

def add(h, w):
    field[h][w + 1] += 1
    field[h + 2][w + 1] += 1
    field[h + 1][w] += 1
    field[h + 1][w + 2] += 1

for h in range(H):
    for w in range(W):
        if S[h][w] == "#":
            add(h, w)
        else:
            field[h+1][w+1] -= 10
        
res = 0
for l in field[1:H+1]:
    if 0 in l[1:W+1]:
        print("No") 
        break
else:
    print("Yes")


Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define int long long
using namespace std;


signed main(){
	int n, ans=0, c=0;
	cin>>n;
	
	for(int i = 1; i <= n; i++){
		if(i%2==0)continue;
		c=0;
		for(int j = 1; j <= i; j++){
			if(i%j==0)c++;
		//	cout<<j<<endl;
		}
		if(c==8)
		{
			ans++;
		//	cout<<i<<endl;
			}
	}
	
	cout<<ans<<endl;
	
	return 0;
}

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

int main() {
  int p;
  int q;
  int r;
  cin >> p >> q >> r;
  int x = p + r;
  int y = q + r;
  int z = p + q;
  cout << min(x, min(y, z)) << endl;
}


Measured memory_bytes: 256
N, M, X = map(int, input().split())
C = []
A = []
for  i in range(N):
    t = list(map(int, input().split()))
    C.append(t[0])
    A.append(t[1:])
    
result = -1
"""
<< bit演算に関する演算子
左辺の値を右辺の値だけ左へシフトすることを意味する

https://www.javadrive.jp/python/num/index4.html

下記の場合、1からNまで2真数でシフトしていく感じ
"""

for i in range(1 << N):
    #初期化
    t = [0] * M
    c = 0
    #print(i)
    for j in range(N):
        #print(j)
        if(i >> j ) & 1 == 0 :
            continue
        c += C[j]
        for k in range(M):
            t[k] += A[j][k]
    if all(x >= X for x in t):
        if result == -1:
            result = c
        else:
            result = min(result, c)
print(result)

Measured memory_bytes: 9220
#include <iostream>
#include <vector>
using namespace std;
typedef pair<long long, long long> P;

int main() {
  long long H; cin >> H;
  vector<P> vec;
  vec.push_back(P(H, 1LL));
  while(true) {
    P le = vec.back();
    if(le.first == 1) break;
    vec.push_back(P(le.first/2, le.second*2));
  }
  long long ans = 0LL;
  for(auto v: vec) {
    ans += v.second;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const ll mod = 1e9 + 7;

int main(){
	ll N, ans = 0, now = 1; cin >> N;
	for(int i=1; i<35; i++){
		now *= 5;
		if(now > N) break;
		ll p = N/2;
		if(N%2 == 0){
			ans += p/now;
		}
	}
	if(N%2==1) cout << 0 << endl;
	else cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#define MAX 100000
#define SENTINEL 2000000000

struct Card {
    char suit;
    int value;
};

struct Card L[MAX / 2 + 2], R[MAX / 2 + 2];

void merge(struct Card A[], int n, int left, int mid, int right)
{
    int i, j, k;
    int n1 = mid - left;
    int n2 = right - mid;
    for (i = 0; i < n1; i++) {
        L[i] = A[left + i];
    }
    for (i = 0; i < n2; i++) {
        R[i] = A[mid + i];
    }
    L[n1].value = R[n2].value = SENTINEL;
    i = j = 0;
    for (k = left; k < right; k++) {
        if (L[i].value <= R[j].value) {
            A[k] = L[i++];
        } else {
            A[k] = R[j++];
        }
    }
}

void mergeSort(struct Card A[], int n, int left, int right)
{
    int mid;
    if (left + 1 < right) {
        mid = (left + right) / 2;
        mergeSort(A, n, left, mid);
        mergeSort(A, n, mid, right);
        merge(A, n, left, mid, right);
    }
}

int partition(struct Card A[], int n, int p, int r)
{
    int i, j;
    struct Card t, x;
    x = A[r];
    i = p - 1;
    for (j = p; j < r; j++) {
        if (A[j].value <= x.value) {
            i++;
            t = A[i];
            A[i] = A[j];
            A[j] = t;
        }
    }
    t = A[i + 1];
    A[i + 1] = A[r];
    A[r] = t;
    return i + 1;
}

void quickSort(struct Card A[], int n, int p, int r)
{
    int q;
    if (p < r) {
        q = partition(A, n, p, r);
        quickSort(A, n, p, q - 1);
        quickSort(A, n, q + 1, r);
    }
}

int main(int argc, char const *argv[])
{
    int n, i, v;
    struct Card A[MAX], B[MAX];
    char S[10];
    int stable = 1;

    scanf("%d", &n);
    
    for (i = 0; i < n; i++) {
        scanf("%s %d", S, &v);
        A[i].suit = B[i].suit = S[0];
        A[i].value = B[i].value = v;
    }

    mergeSort(A, n, 0, n);
    quickSort(B, n, 0, n - 1);

    for (i = 0; i < n; i++) {

        if (A[i].suit != B[i].suit) stable = 0;
    }
    
    if (stable == 1) {
        printf("Stable\n");
    } else {
        printf("Not stable\n");
    }
    for (i = 0; i < n; i++) {
        printf("%c %d\n", B[i].suit, B[i].value);
    }

    return 0;
}



Measured memory_bytes: 4040
h={};("0%b"%gets[/\d+$/]).scan(/./){h[eval"0b#$`0".+$&<?1?$':?1*$'.size]=0};$<.map{|s|a,b=s.split.map &:to_i;h.map{|k,_|a|k>k||h[k]+=b}};p h.values.max

Measured memory_bytes: 39164
import java.util.Scanner;

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

		int S, h, m, s;

		Scanner scan = new Scanner(System.in);

		S = Integer.parseInt(scan.next());

		if ((S >= 0) && (S < 86400)) {

			h = S / (60 * 60);
			m = (S % (60 * 60)) / 60;
			s = (S % (60 * 60)) % 60;
			System.out.println(h + ":" + m + ":" + s);
		}
	}
}

Measured memory_bytes: 26000
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cstring>
#include <math.h>
#include <bitset>
#include <queue>
#include <set>
#include <iomanip>
#include <math.h>
#include <assert.h>
// #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr long long int INFLL = 1001001001001001LL;
constexpr long long int infll = 1001001001001001LL;
constexpr int INF = 1000000007;
constexpr int inf = 1000000007;
const int mod = 1000000007;

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;
}

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

ll lcm(ll a, ll b)
{
    return a / gcd(a, b) * b;
}

inline double nCr(const int n, int r)
{
    if (n == 0)
    {
        return 0;
    }
    if (r == 0)
    {
        return 1;
    }
    if (r == 1)
    {
        return n;
    }
    if (n == r)
    {
        return 1;
    }

    if (r > n / 2)
    {
        r = n / 2;
    }

    double result = 1;
    for (double i = 1; i <= r; i++)
    {
        result *= (n - i + 1) / i;
    }

    return (result);
}

template <typename T>
T seinomi(T a)
{
    if (a > 0)
    {
        return a;
    }
    else
    {
        return 0;
    }
}

template <typename T>
map<T, T> soinsuubunkai(T n) //連想配列[素因数f.first][個数f.second]
{
    map<T, T> ret;
    for (T i = 2; i * i <= n; i++)
    {
        while (n % i == 0)
        {
            ret[i]++;
            n /= i;
        }
    }
    if (n != 1)
        ret[n] = 1;
    return ret;
}

template <typename T>
T ketasuu(T num)
{
    return std::to_string(num).length();
}

int kaizyou(int k)
{
    int sum = 1;
    for (int i = 1; i <= k; ++i)
    {
        sum *= i;
    }
    return sum;
}

template <class ForwardIt, class T>
void iota(ForwardIt first, ForwardIt last, T value)
{
    while (first != last)
    {
        *first++ = value;
        ++value;
    }
}

//nの階乗を計算
int factorial(int n)
{
    int answer = 1;
    while (n > 1)
    {
        answer *= n;
        n--;
    }
    return answer;
}
int comb(int n, int r)
{
    return factorial(n) / (factorial(r) * factorial(n - r));
}

long long modpow(long long a, long long n, long long mod)
{
    long long res = 1;
    while (n > 0)
    {
        if (n & 1)
            res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

//小数点以下10桁テンプレート（main関数内の最初に貼付け）
//std::cout << std::fixed << std::setprecision(10);

//----------------------------------------------------------------


int main(){
ll a,b,c,d;
cin>>a>>b>>c>>d;
if(a+b<c+d){
    cout<<"Right"<<endl;
}else if(a+b==c+d){
    cout<<"Balanced"<<endl;
}else{
    cout<<"Left"<<endl;
}

}









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

vector<int> to[200005];
vector<int> ans;

void dfs(int v,int p=-1){
  for(int b:to[v]){
    if(b==p)continue;
    ans[b] += ans[v];
    dfs(b,v);
  }
}

int main(){
  int n,q;
  cin >> n >> q;
  rep(i,n-1){
    int a,b;
    cin >> a >> b;
    a--; b--;
    to[a].push_back(b);
    to[b].push_back(a);
  }
  ans.resize(n);
  rep(i,q){
    int p,x;
    cin >> p >> x;
    p--;
    ans[p] += x;
  }
  dfs(0);
  rep(i,n) cout << ans[i] << endl;
}


Measured memory_bytes: 23424
#include <bits/stdc++.h>
using namespace std;
struct Fast { Fast() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20);} } fast;

long long modpow(long long m, long long n) {
    if (n == 0) return 1;
    if (n % 2 == 0) {
        long long t = modpow(m, n / 2);
        return t / 2;
    } else {
        return modpow(m, n - 1) * m;
    }
}

int main() {
    vector<int> dp(10001);
    dp[0] = 0;
    int n, W;
    cin >> n >> W;
    vector<int> vs(n), ws(n);
    for (int i = 0; i < n; i++) cin >> vs[i] >> ws[i];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 10000; j++) {
            if (j + ws[i] > 10000) continue;
            dp[j + ws[i]] = max(dp[j + ws[i]], dp[j] + vs[i]);
        }
    }
    cout << dp[W] << endl;
}


Measured memory_bytes: 3256
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<cmath>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<numeric>
#include<functional>
#include<algorithm>
#include<bitset>
#include<tuple>
#include<unordered_set>
#include<random>
#include<array>
#include<cassert>
using namespace std;
#define INF (1<<29)
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define uniq(v) v.erase(unique(all(v)),v.end())




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

	int n;
	int a[2][100];
	cin >> n;
	rep(i,2)rep(j,n) {
		cin >> a[i][j];
	}
	int ans = 0;
	rep(x, n) {
		int c = 0;
		rep(i, x + 1)c += a[0][i];
		for (int i = x; i < n; i++)c += a[1][i];
		ans = max(ans, c);
	}
	cout << ans << endl;


	return 0;
}

Measured memory_bytes: 256
// abc117_b
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<unordered_map>
#include<utility>
#include<cmath>
#include<random>
#include<cstring>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#include<typeinfo>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
#define FOR(i,a) for(auto i:a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
#define show1d(v) rep(i,v.size())cout<<" "<<v[i];cout<<endl<<endl;
#define show2d(v) rep(i,v.size()){rep(j,v[i].size())cout<<" "<<v[i][j];cout<<endl;}cout<<endl;
using namespace std;
typedef long long ll;
typedef int Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;}
template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;}
const double PI=acos(-1);
const double EPS=1e-9;
Def inf = sizeof(Def) == sizeof(long long) ? 2e18 : 1e9+10;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int main(int argc, char *argv[])
{
  int n,sum=0;
  cin>>n;
  vi l(n);
  rep(i,n){
    cin>>l.at(i);
  }

  sort(all(l));
  for(int i=0;i<n-1;++i) {
    sum+=l.at(i);
  }
  if (l.at(n-1)<sum) {
    cout<<"Yes"<<endl;
  } else {
    cout<<"No"<<endl;
  }

  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include <algorithm>
#include <functional>
#include<vector>
#include<unordered_map>
#include<queue>
#include<string>

using namespace std;
class CompareFirst
{
public:
    bool operator()(pair<int,int> n1,pair<int,int> n2) {
        return n1.first>n2.first; //>:¸‡@<:~‡
    }
};


int main(){

string s,prev,tmp;
int a,b,c,i,j,k,n,ans;
vector<string> lst;
vector<int> cnt;

//unordered_map<string,int> mp;

//priority_queue<int> pq; // default ‘å‚«‚¢‡
//priority_queue<pair<int,int>,vector<pair<int,int>>,CompareFirst pq;

cin >> s;

n = s.size();
ans = 0;

prev="";
tmp = "";
for(i=0;i<n;++i){
  if(prev == ""){
    prev = s[i];
    ++ans; 
  }else{
    tmp += s[i];
    if(prev == tmp){
    }else{
      ++ans;
      prev = tmp;
 //     cout << prev << endl;
      tmp = "";
    }
  }
}
if(prev != tmp && tmp != "")++ans;
cout << ans << endl;

return 0;

}

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

int c[500],v[500][3];
int dp[500][500];
int main(){
    int n,m;
    while(cin>>n>>m){
        rep(i,n){
            string s;getline(cin,s);getline(cin,s);
            cin>>c[i];
            rep(j,3)cin>>v[i][j];
        }
        int Max=0;
        rep(t,3){
            memset(dp,0,sizeof(dp));
            rep(i,n){
                rep(j,m+1){
                    dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
                    if(j+c[i]<=m)
                        dp[i+1][j+c[i]]=max(dp[i+1][j+c[i]],dp[i+1][j]+v[i][t]);
                }
            }
            Max=max(Max,dp[n][m]);
        }
        cout<<Max<<endl;
    }
}

Measured memory_bytes: 4124
#include<iostream>
#include<algorithm>

#define INFTY 1000000001

using namespace std;

int n, s[500010], cnt = 0;

void merge(int *A, int left, int mid, int right){
  int n1 = mid - left;
  int n2 = right - mid;
  int i, j;

  //generate L[0...n1], R[0...n2]
  int L[n1 + 10], R[n2 + 10];
  for(i = 0;i < n1;i++) L[i] = A[left + i];
  for(i = 0;i < n2;i++) R[i] = A[mid + i];

  L[n1] = INFTY;
  R[n2] = INFTY;

  i = 0;
  j = 0;

  for(int k = left;k < right;k++){
    cnt++;
    if(L[i] <= R[j]){
      A[k] = L[i];
      i++;
    }else{
      A[k] = R[j];
      j++;
    }
  }
}

void mergeSort(int *A, int left, int right){
  if(left + 1 < right){
    int mid = (left + right)/2;
    mergeSort(A, left, mid);
    mergeSort(A, mid, right);
    merge(A, left, mid, right);
  }
}

int main(){

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

  mergeSort(s, 0, n);

  for(int i = 0;i < n;i++){
    cout << (i?" ":"");
    cout << s[i];
  }
  cout << endl;

  cout << cnt << endl;

  return 0;
}



Measured memory_bytes: 7004
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const LL INF=1e18;
const int MAXN=2e5+100;
const double eps=1e-10;
bool vis[MAXN];
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF){
        int u,v;
        bool flag=false;
        for(int i=1;i<=n;i++)
            vis[i]=false;
        for(int i=1;i<=m;i++){
            scanf("%d%d",&u,&v);
            if(flag) continue;
            if(u==1){
                if(vis[v]){
                    flag=true;
                }
                vis[v]=true;
            }else if(v==n){
                if(vis[u]){
                    flag=true;
                }
                vis[u]=true;
            }
        }
        if(flag) printf("POSSIBLE\n");
        else printf("IMPOSSIBLE\n");
    }
    return 0;
}

Measured memory_bytes: 384
# -*- coding: utf-8 -*-

N = int(input())
items = []
for i in range(N):
    S, P = input().split()
    items.append({'id': i+1, 'S': S, 'P': int(P), 'pri': i})

sorted_items = sorted(
  items,
  key = lambda x: (x['S'], -x['P'])
)

for i in range(N):
    sorted_items[i].update(pri=i+1)

sorted_items2 = sorted(
  sorted_items,
  key = lambda x:x['pri']
)

for i in sorted_items2:
    print(i['id'])


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

int main(){
	int N,K;
	cin >> N >> K;
	string S;
	cin >> S;
	vector<int> v;
	
	if(S[0] == '0'){
		v.push_back(0);
	}
	
	rep(i,N){
		int count = 0;
		if(S[i] == '0'){
			while(S[i] == '0'){
				count++;
				i++;
			}
			v.push_back(count);
			i--;
		}else{
			while(S[i] == '1'){
				count++;
				i++;
			}
			i--;
			v.push_back(count);
		}
	}
	if(S[S.size()-1] == '0') {
		v.push_back(0);
	}
	
	rep(i,v.size()-1){
		v[i+1] += v[i];
	}
	
	int n = v.size();
	int ans = v[min(2*K,n-1)];
	
	
	//偶数番目の添字から始まる２K＋1個の和の最大値を求める。
	for (int i = 0; i < n; i+=2) {
		int left = i;
		int right = i+2*K;
		ans = max(ans, v[min(right,n-1)]-v[max(left-1,0)]);
	}
	
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1020
#include<stdio.h>
int max(int a, int b){return a<b?b:a;}
int n, a, i;
int h[20], m;
int main(void){
  scanf("%d", &n);
  for(i=0; i<n; i++){
    scanf("%d", h+i);
    if(h[i]>=m){a++;}
    m = max(m, h[i]);
  }
  printf("%d\n", a);
}


Measured memory_bytes: 128