akhauriyash/Code-Regression huggingface dataset:
class Stack:
    def __init__(self,arg_size):
        self.size = arg_size
        self.stack = [None] * self.size
        self.head = 0
        self.tail = 0

    def is_empty(self):
        return self.tail == self.head

    def push(self,arg_object):
        self.stack[self.tail] = arg_object
        self.tail += 1

    def pop(self):
        self.tail -= 1
        return self.stack[self.tail]

    def top(self):
        return self.stack[self.head]

SIZE = 105
NUM = Stack(SIZE)

input_str = list(map(str,input().split()))

for i in range(len(input_str)):
    ch = input_str[i]
    if ch in ['+','-','*']:
        num_2 = NUM.pop()
        num_1 = NUM.pop()
        num = 0
        if ch =='+':
            num =num_1+num_2
        elif ch =='-':
            num = num_1 - num_2
        else:
            num = num_1 * num_2
        NUM.push(num)
    else:
        NUM.push(int(ch))
print(NUM.top())


Measured memory_bytes: 5604
import java.util.*;
import java.io.*;

public class Main{
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		String[] cmd=br.readLine().split(" ");
		int n=Integer.valueOf(cmd[0]);
		cmd=br.readLine().split(" ");
		int[] cnt=new int[1000001];
		HashMap<Integer,Integer> check=new HashMap<>();
		HashMap<Integer,Integer> map=new HashMap<>();
		int[] arr=new int[n];
		int max=0;
		for(int i=0;i<n;i++)
		{
			arr[i]=Integer.valueOf(cmd[i]);
			cnt[arr[i]]++;
			if(!map.containsKey(arr[i]))
			map.put(arr[i], 1);
			if(max<arr[i])
				max=arr[i];
		}
		for(int i=0;i<n;i++)
		{
			int x=arr[i];
			int y=max/arr[i];
			if(cnt[x]>1)
			{
				if(!check.containsKey(x))
					check.put(x,1);
			}
			for(int j=2;j<=y;j++)
			{
				if(map.containsKey(j*x))
				{
					if(!check.containsKey(j*x))
					check.put(j*x,1);
				}
			}
		}
		int ans=0;
		for(int i=0;i<n;i++)
		{
			if(!check.containsKey(arr[i]))
				ans++;
		}
		System.out.println(ans);
	}

}


Measured memory_bytes: 96824
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  ll n;
  cin >> n;
  ll ans=0;
  ans+= (n/500)*1000;
  n=n%500;
  ans+=(n/5)*5;
  cout << ans;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void){
   
   int i;
   int N = 5;
   int Antena[N];
   
   for(i = 0;i < N;i++){
      scanf("%d",&Antena[i]);
   }
   
   int k;
   scanf("%d",&k);
   
   int j;
   int flag = 0;
   for(i = 0;i < N;i++){
      for(j = i + 1;j < N;j++){
         if(abs(Antena[i] - Antena[j]) > k){
            flag = 1;
            break;
         }
      }
   }
   
   if(flag == 1){
      printf(":(\n");
   }
   else {
      printf("Yay!\n");
   }
   
   
   
   return 0;
}


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


int main(){

	int H,W;
	cin>>H>>W;
	
	vector<vector<int>> dis(10,vector<int>(10,Inf));
	
	for(int i=0;i<10;i++){
		for(int j=0;j<10;j++){
			cin>>dis[i][j];
		}
	}
	
	for(int k=0;k<10;k++){
		for(int i=0;i<10;i++){
			for(int j=0;j<10;j++){
				if(dis[i][j] > dis[i][k] + dis[k][j]){
					dis[i][j] = dis[i][k] + dis[k][j];
				}
			}
		}
	}
	
	int ans = 0;
	
	for(int i=0;i<H;i++){
		for(int j=0;j<W;j++){
			int a;
			cin>>a;
			if(a<0)continue;
			ans += dis[a][1];
		}
	}
	
	cout<<ans<<endl;
	
    return 0;
}



Measured memory_bytes: 256
//AtCoder ABC115 B - Christmas Eve Eve
#include <bits/stdc++.h>
using namespace std;
using ll=int64_t;
int main() {
    ll N; cin>>N;
    vector<ll> pn(N);
    for(auto&& p:pn){
        cin>>p;
    }
    sort(pn.begin(),pn.end(),greater<ll>());
    ll ans=pn[0]/2;
    for(ll i=1;i<pn.size();++i){
        ans+=pn[i];
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
from itertools import combinations_with_replacement
n,m,q=map(int,input().split())
abcd=[list(map(int,input().split())) for i in range(q)]
ans=0
for a in combinations_with_replacement(range(1,m+1),n):
  x=0
  for i in range(q):
    if a[abcd[i][1]-1]-a[abcd[i][0]-1]==abcd[i][2]:
      x=x+abcd[i][3]
  ans=max(ans,x)
print(ans)

Measured memory_bytes: 9060
#include <bits/stdc++.h>
#define eps 1e-3
#define pi acos(-1.0)
#define inf 0x3f3f3f3f
#define debug1 cout<<"&&";
#define debug2 cout<<"**";
#define pb push_back
#define ms(a, x) memset(a, x, sizeof(a))
#define forn(i, n) for(int i = 0; i < n; ++i)
#define for1(i, n) for(int i = 1; i <= n; ++i) 
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int mod = 1e9;
const int N = 1e5 + 10;
/*=======================================================================*/

ll n, W, w[N], v[N], f[N];
ll ans = 0;
int main() {
  cin >> n >> W;
  ms(f, inf);
  f[0] = 0;
  for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];

  for (int i = 1; i <= n; i++) {
     for (int l = 1e5; l >= v[i]; l--) {
        if (f[l - v[i]] + w[i] < f[l]) {
         //   debug1
            f[l] = f[l - v[i]] + w[i];
         }
         if(f[l] <= W) ans = max(ans, (ll)l);
     }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1024
//#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
//#include <queue>
//#include <stack>
#include <cstring>
#include <cassert>

using namespace std;

#ifdef LOCAL_DEBUG
#include <local_debug.h>
#define DEBUG(x...) cerr << #x << " = "; DBG::_print(x)
#else
#define DEBUG(x...)
#endif

#define SZ(a) int((a).size())
#define REP(i,n) for(int i=0,_n=(n);i<_n;++i)
#define FOR(i,a,b) for(int i=(a),_b=(b);i<=_b;++i)

typedef long long llong;
typedef vector<int> VI;
typedef vector<VI> VVI;

const llong INF = 1e18;

#define MAXN 200004
int N;
llong A[MAXN];

bool cached[3][MAXN];
llong memo[3][MAXN];
llong go(int nskips, int n) {
   if (n >= N) {
      return (nskips == 2) ? -INF : 0;
   }
   llong& res = memo[nskips][n];
   if (!cached[nskips][n]) {
      res = -INF;
      if (nskips > 0)
         res = go(nskips-1, n+1);
      res = max(res, go(nskips, n+2) + A[n]);
      cached[nskips][n] = true;
   }
   return res;
}

int main(int argc, char* argv[]) {
   ios_base::sync_with_stdio(false); 
   cin.tie(nullptr);

   cin >> N;
   assert(N < MAXN);

   REP(i, N)
      cin >> A[i];

   llong res = go(N & 1 ? 2 : 1, 0);
   cout << res << '\n';

   return 0;
}


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

using namespace std;

#define all(c) (c).begin(), (c).end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

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

string s;
int f(char c) {
    int ret = 0;
    int t = -1;
    rep(i, s.size()) {
        if (s[i] == c) {
            ret = max(ret, i - t - 1);
            t = i;
        }
    }
    int n = s.size() - 1;
    return max(ret, n - t);
}
int main() {
    cin >> s;
    int ans = 1e8;
    rep(i, 26) ans = min(ans, f(i + 'a'));
    cout << ans << endl;

    return 0;
}

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

using namespace std;

int v[100010];

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

    int poz = -1;
    for (int i = 1; i <= n; ++i)
    {
        cin >> v[i];
        if (i > 1 && v[i] + v[i - 1] >= l) poz = i;
    }

    if (poz == -1)
    {
        cout << "Impossible\n";
        return 0;
    }

    cout << "Possible\n";

    for (int i = 1; i < poz - 1; ++i)
        cout << i << '\n';

    for (int i = n - 1; i >= poz; --i)
        cout << i << '\n';

    cout << poz - 1 << '\n';

    return 0;
}


Measured memory_bytes: 1152
import scala.io.StdIn.readLine

class Dice(var d:List[Int]) {
  val fs = (x:List[Int]) => x match {case List(x1,x2,x3,x4,x5,x6) => List(x5,x1,x3,x4,x6,x2) }
  val fn = (x:List[Int]) => x match {case List(x5,x1,x3,x4,x6,x2) => List(x1,x2,x3,x4,x5,x6) }
  val fw = (x:List[Int]) => x match {case List(x1,x2,x3,x4,x5,x6) => List(x3,x2,x6,x1,x5,x4) }
  val fe = (x:List[Int]) => x match {case List(x3,x2,x6,x1,x5,x4) => List(x1,x2,x3,x4,x5,x6) }

  def roll(dir:Char)  =
    d = dir match {
      case 'S' => fs(d)
      case 'N' => fn(d)
      case 'W' => fw(d)
      case 'E' => fe(d)
    }

  def getTopFace() = d(0)
}

object Main extends App {
  val faces = readLine.split(" ").map(_.toInt).toList
  val dice = new Dice(faces)

  readLine.foreach { dice.roll _ }
  println(dice.getTopFace)
}

Measured memory_bytes: 44100
package main

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

const SPACE = '.'
const BLOCK = '#'

type Point struct {
	x int
	y int
	d int
}

type Queue []Point

func (q *Queue) push(x Point) {
	*q = append(*q, x)
}

func (q *Queue) pop() Point {
	x := (*q)[0]
	*q = (*q)[1:]
	return x
}

func (q *Queue) isEmpty() bool {
	return len(*q) == 0
}

var dx = []int{-1, 0, 1, 0}
var dy = []int{0, 1, 0, -1}
var sc = bufio.NewScanner(os.Stdin)

func main() {
	r := bufio.NewReader(os.Stdin)

	var h, w int
	fmt.Fscan(r, &h)
	fmt.Fscan(r, &w)

	grid := make([]string, h)

	spaceCnt := 0
	for i := 0; i < h; i++ {
		fmt.Fscan(r, &grid[i])
		for j := 0; j < w; j++ {
			if grid[i][j] == SPACE {
				spaceCnt++
			}
		}
	}
	spaceCnt-- // without start point

	seen := make([][]bool, h)
	for i := range seen {
		seen[i] = make([]bool, w)
	}

	que := Queue{}
	que.push(Point{x: 0, y: 0})
	d := 0
	for !que.isEmpty() {
		p := que.pop()
		if p.x == w-1 && p.y == h-1 {
			d = p.d
			break
		}
		if !seen[p.y][p.x] {
			r = bufio.NewReader(os.Stdin)
		}

		for i := 0; i < 4; i++ {
			nx := p.x + dx[i]
			ny := p.y + dy[i]
			if 0 <= nx && nx < w && 0 <= ny && ny < h && grid[ny][nx] != BLOCK && !seen[ny][nx] {
				seen[ny][nx] = true
				que.push(Point{x: nx, y: ny, d: p.d + 1})
			}
		}
	}
	if d > 0 {
		fmt.Println(spaceCnt - d)
	} else {
		fmt.Println(-1)
	}
}


Measured memory_bytes: 768
#include<iostream>
using namespace std;
typedef long long ll;
ll a,b,c,s,kai=0;
int main(){
  cin>>a>>b>>c;
  while(a%2==0&&b%2==0&&c%2==0&&kai<50){
    kai++;
    s=a+b+c;
    a=(s-a)/2;
    b=(s-b)/2;
    c=(s-c)/2;
  }
  cout <<(kai==50?-1:kai);
}

Measured memory_bytes: 256
from collections import deque
H,W,N=map(int,input().split())
e='X'*(W+2)
M=e+''.join('X'+input()+'X'for _ in[0]*H)+e
m=(1,-1,W+2,-W-2)
def f(s,g):
 p,t=s,0
 q=deque()
 b=[1]*len(M);b[s]=0
 while 1:
  for d in m:
   n=p+d
   if'X'!=M[n]and b[n]:
    if M[n]==g:return(n,t+1)
    b[n]=0;q.append([n,t+1])
  p,t=q.popleft()
s=M.find('S')
a=0
for i in range(1,N+1):
 s,t=f(s,str(i))
 a+=t
print(a)


Measured memory_bytes: 14944
#include <stdio.h>
int main(){
  long long n,p,f[99],a[99],ans=1,c,i,x=0;
  scanf("%lld%lld",&n,&p);
  for(i=2;i*i<=p;i++){c=0;while(p%i==0){p/=i;c++;}if(c){f[x]=i;a[x++]=c;}}
  if(p-1){f[x]=p;a[x++]=1;}
  for(i=0;i<x;i++)for(c=1;c*n<=a[i];c++)ans*=f[i]; 
  printf("%lld",ans);
}

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

int main(){
	ll a, b, k;
  	cin >> a >> b >> k;
  
  	ll x = min(a, k);
  	a -= x;
  	k -= x;
  	b -= min(b, k);
  	cout << a << " " << b << endl;
}

Measured memory_bytes: 256
inputs = input().split()
N = int(inputs[0])
A = int(inputs[1])
B = int(inputs[2])

ans = 0
for i in range(1,N+1):
    num = 0
    for j in str(i):
        num += int(j)
    if num >= A and num <= B:
        ans += i
print(ans)

Measured memory_bytes: 3064
#include<iostream>
#include<vector>
#include<string>
#include<cmath>
#include<algorithm>
#include <numeric>
#include<map>
#include<unordered_map>
#include <queue>
 
using namespace std;
using ll=long long;
#define rep(i,n)  for(ll i=0;i<n;++i)
#define all_map(itr,mp) for(auto itr=mp.begin();itr!=mp.end();itr++)
#define ALL(a) (a).begin(),(a).end()

int main(){
    int a[4];
    cin >> a[0] >> a[1] >> a[2] >> a[3];

    bool is[4] = {};
    rep(i, 4){
        if(a[i]==1)is[0]=true;
        else if(a[i]==9)is[1]=true;
        else if(a[i]==7)is[2]=true;
        else if(a[i]==4)is[3]=true;
        else{
            cout << "NO\n";
            return 0;
        }
    }
    if(is[0]&is[1]&is[2]&is[3])cout << "YES\n";
    else cout << "NO\n";
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
long long h[200010],sum;
int main()
{
	int n,k,i;
	cin>>n>>k;
	for(i=0;i<n;i++)
		cin>>h[i];
	sort(h,h+n);
	for(i=0;i<n-k;i++)
		sum+=h[i];
	cout<<sum;
	return 0;
}

Measured memory_bytes: 1792
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
  long k = sc.nextLong();
  long a = sc.nextLong();
  long b = sc.nextLong();
  long ans = 0;
  if(b - a <= 2){
    ans = k + 1;
  }
  else{
    if((k - a + 1)%2 == 0){
    ans = (long)((k-a+1)/2) * (b-a) + a;
    }
    else{
      ans = (long)((k-a+1)/2) * (b-a) + a  + 1;
    }
  }
  System.out.println(ans);
}}
  

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

int main() {
    long long K, A, B;
    cin >> K >> A >> B;
    long long ret = 1; // number of biscuit

    if (
        B-A > 2 // 錬金したほうが得
        || K < A - 1 + 2// 錬金できるか　A枚のビスケット, -1 最初の一枚, +2 錬金に必要な回数
    ) {
        // A になるまでたたく
        K -= (A - 1);
        ret = A;
        
        // 回数限度まで錬金する
        int num = K / 2; // 錬金回数
        K -= num * 2; // 錬金後の残回数
        ret += num * (B - A);

        // 最後の調整
        ret += K;
    } else { // たたいた方が得
        ret += K;
    }

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

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

using namespace std;

long long a[200001];

int main()
{
	int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        a[i] += a[i-1];
    }
    long long ans = a[n];
    for (int i = 2; i <= n - 2; ++i) {
        int j = upper_bound(a+1,a+i,a[i]/2) - a;
        int k = upper_bound(a+i+1,a+n+1,(a[i]+a[n])/2) - a;
        for (int i0 = j - 2; i0 <= j + 2; ++i0)
            for (int i2 = k - 2; i2 <= k + 2; ++i2) {
                if (i <= i0 || i2 <= i || i0 < 1 || i2 >= n)
                    continue;
                long long t[4] = {a[i0],a[i]-a[i0],a[i2]-a[i],a[n]-a[i2]};
                sort(t,t+4);
                ans = min(ans, t[3]-t[0]);
            }
    }
    cout << ans << endl;
}

Measured memory_bytes: 1792
// --------------
// Tejas Pandey  |
// 13 - 06 - 20  |
// ATcoder RC    |
// --------------

#include <bits/stdc++.h>
using namespace std;
     
#define mod 1000000007
#define vi vector<int>
typedef long long int ll;
     
int main (void){
  //freopen("in.txt","r",stdin);
  //freopen("out.txt","w",stdout);
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  string s;
  cin >> s;
  cout << s[0] << s[1] << s[2];
  return 0;
}


Measured memory_bytes: 3648
#include<stdio.h>
int main(void)
{
	int a,b,c,d;
	int x,y,z;
	scanf("%d %d %d %d",&a,&b,&c,&d);
	if(a<b){
		x=b-a;
	}
	else{
		x=a-b;
	}
	if(b<c){
		y=c-b;
	}
	else{
		y=b-c;
	}
	if(a<c){
		z=c-a;
	}
	else{
		z=a-c;
	}
	if(x<=d&&y<=d||z<=d){
		printf("Yes\n");
	}
	else{
		printf("No\n");
	}
	return 0;
}


Measured memory_bytes: 128
n, a, b = map(int, input().split())
cities = list(map(int, input().split()))
hirou = 0
for index in range(n-1):
  kyori = cities[index+1] - cities[index]
  if kyori*a > b:
    hirou += b
  else:
    hirou += kyori * a
print(hirou)
      

Measured memory_bytes: 15020
import sys
import Queue

n = int(raw_input())

graph = dict()
color = [-1 for i in range(0, n)]
for i in range(0, n - 1):
    u, v, w = map(int, raw_input().split(" "))
    if (u - 1) in graph:
        graph[u - 1].append((v-1, w))
    else:
        graph[u - 1] = [(v-1, w)]

    if (v - 1) in graph:
        graph[v - 1].append((u - 1, w))
    else:
        graph[v - 1] = [(u - 1, w)]

# for start, value_list in graph.items():
#     for end, weight in value_list:
#         print("%s -> %d (%d)" % (start, end, weight))

queue = Queue.Queue()
sum = 0
next_check = 0

while sum < n:

    for i in range(next_check, n):
        if color[i] < 0:
            queue.put(i)
            color[i] = 0
            sum += 1
            next_check = i
            break

    while not queue.empty():
        current_node = queue.get()
        if current_node in graph:
            for end, weight in graph[current_node]:
                if color[end] < 0:
                    color[end] = (color[current_node] + weight % 2) % 2
                    queue.put(end)
                    sum += 1

for node in range(0, n):
    print(color[node])


Measured memory_bytes: 49172
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <numeric>

using namespace std;

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

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

    int count = 0;
    rep(i, a+1){
        rep(j, b+1){
            rep(k, c+1){
                if(i * 500 + j * 100 + k * 50 == x) count ++;
            }
        }
    }

    cout << count << endl;
}

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

int main(){
    long long q, h, s, d;
    long long n;
    cin >> q >> h >> s >> d;
    cin >> n;

    long long ans = 0;

    if(q*2 < h){
        h = q*2;
    }

    if(h*2 < s){
        s = h*2;
    }

    if(s*2 < d){
        d = s*2;
    }

    cout << (n / 2) * d + (n % 2) * s << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int INF=1001001001;
int main() {
    int n;cin>>n;
    vector<long long> h(n);
    for(int i=0;i<n;i++)cin>>h[i];
    reverse(h.begin(),h.end());
    int ans=0;
    int val=0;
    for(int i=1;i<n;i++){
        if(h[i-1]<=h[i])val++;
        else val=0;
        ans=max(ans,val);
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <sstream>
#include <iomanip> 
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <bitset>

using namespace std;


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

	long long a, b, n, x, ans;
	cin >> a >> b >> n;
	x = min(b - 1, n);

	ans = (a * x / b) - a * (x / b);
	cout << ans << "\n";


	return 0;
}




Measured memory_bytes: 3648
#include <bits/stdc++.h>
using namespace std;
const int MAX = 100001;
const int MOD = pow(10, 9) + 7;
// dp[i] : 13で割ったあまりが i である数値の個数
int dp[13], new_dp[13];
char s[MAX];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    scanf("%s", s);

    dp[0] = 1;
    int64_t mul = 1;
    for (int i = 0; i < strlen(s); i++) {
        if (s[strlen(s) - 1 - i] == '?') {
            for (int j = 0; j < 10; j++) {
                for (int k = 0; k < 13; k++) {
                    new_dp[(mul * j + k) % 13] += dp[k];
                    new_dp[(mul * j + k) % 13] %= MOD;
                }
            }
        } else {
            int j = s[strlen(s) - 1 - i] - '0';
            for (int k = 0; k < 13; k++) {
                new_dp[(mul * j + k) % 13] += dp[k];
                new_dp[(mul * j + k) % 13] %= MOD;
            }
        }

        for (int l = 0; l < 13; l++) {
            dp[l] = new_dp[l];
            new_dp[l] = 0;
        }
        mul *= 10;
        mul %= 13;
    }

    cout << dp[5] << endl;
    return 0;
}


Measured memory_bytes: 384
#include <iostream>
 using namespace std;
 int main(){
 int D;
 cin >> D;
 string ans;
 if(D == 25) ans = "Christmas";
 else if(D == 24) ans = "Christmas Eve";
 else if(D == 23) ans = "Christmas Eve Eve";
 else ans = "Christmas Eve Eve Eve";
 cout << ans << endl;
 }


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

using namespace std;

/* typedef */

typedef long long ll;

/* class */
/* constant */

const int INF = 1 << 30;
const int MAX = 100000;
const int mod = 1000000007;
const double pi = 3.141592653589;
/* global variables */

/* function */
void printVec(vector<int> &vec);
/* main */
int main() {

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

    do {
        printVec(v);
    } while (next_permutation(v.begin(), v.end()));

}

void printVec(vector<int> &vec) {

    for (int i = 0; i < vec.size(); i++) {
        if (i) cout << ' ';
        cout << vec[i];
    } cout << '\n';
}



Measured memory_bytes: 3116
#include <iostream>

using namespace std;

int main(void){
  int N, K;
  string S;

  cin >> N >> S >> K;

  char target = S[K-1];

  for (int i = 0; i < N; i++) {
    if (S[i] != target) {
      S[i] = '*';
    }
  }

  cout << S << '\n';

  return 0;
}

Measured memory_bytes: 256
from collections import defaultdict
H, W, M = map(int, input().split())
tate = defaultdict(int)
yoko = defaultdict(int)
T = {}
for i in range(M):
    h, w = map(int, input().split())
    tate[h-1] += 1
    yoko[w-1]+= 1
    T[(h-1, w-1)] = 1

tate = sorted(tate.items(), key=lambda x:x[1], reverse=True)
yoko = sorted(yoko.items(), key=lambda x:x[1], reverse=True)
tate_m = tate[0][1]
yoko_m = yoko[0][1]
ans = 0
for i in range(len(tate)):
    if ans == tate_m + yoko_m:
        break
    if tate[i][1] == tate_m:
        for j in range(len(yoko)):
            if yoko[j][1] == yoko_m:
                if (tate[i][0], yoko[j][0]) in T:
                    ans = max(ans, tate_m + yoko_m - 1)
                else:
                    ans = max(ans, tate_m + yoko_m)
            else:
                break
    else:
        break
print(ans)

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

int main() {
  int n;
  int m;
  cin >> n >> m;
  vector<int> a(n);
  for(int i = 0; i < n; i++)
    cin >> a.at(i);
  sort(a.begin(),a.end());
  int j = 0;
  while(j < m){
    int amax = a.at(n-1);
    for(int k = n-1; k >= 0; k--){
      if(a.at(k) >= amax/2){
        a.at(k) /= 2;
        j++;
        if(j == m)
          break;
      }
      else{
        sort(a.begin(),a.end());
        break;
      }
    }
  }
  long long ans = 0;
  for(int i : a)
    ans += i;
  cout << ans << endl;
}



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

#define ll long long int
#define pf push_front
#define mod  1000000007
#define inf  1000000000000000000
#define pi  acos(-1.0)
#define maxn  1000009
#define endl '\n'
#define sorted(s)  sort(s.begin(),s.end())
#define reversed(s) reverse(s.begin(),s.end())
#define sortarr(a) sort(a,a+n)
#define slc(n) scanf("%I64d", &n)
#define sl(n)  scanf("%lld", &n)
#define sf(n)  scanf("%lf", &n)
#define si(n)  scanf("%d", &n)
#define sch(n)  scanf(" %c", &n)
#define ss(n)  scanf("%s", n)
#define prf printf
#define pb  push_back
#define fr first
#define sc second
#define all(a)  a.begin(),a.end()
#define forl(n) for(i=0;i<n;i++)
#define ison(n,j) (n&(1LL<<j))
#define _fastio  ios_base:: sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
ll con[65],c[65];
int main()
{
   ll n,i,j,res=0;
   cin>>n;
   ll a[n+5];
   for(i=0;i<n;i++)
    cin>>a[i];
   for(i=0;i<n;i++)
   {
       for(j=0;j<64;j++)
       {
           if((bool)(a[i]&(1LL<<j)))
            con[j]++;
           else
            c[j]++;
       }
   }
   for(i=0;i<64;i++)
    {
        res+=(((con[i]*c[i])%mod)*((1LL<<i)%mod))%mod;//,cout<<con[i]<<" "<<c[i]<<endl;
        res%=mod;
    }
   cout<<res%mod<<endl;

    return 0;
}

Measured memory_bytes: 5900
#include<cstdio>
#include<algorithm>
using namespace std;
int N;
int main() {
	#ifdef LOACL
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
	#endif
	scanf("%d",&N);
	long long ans1=0,ans2=0;
	for(int i=1;i<=N;i++) {
		long long x1,x2;
		scanf("%lld %lld",&x1,&x2);
		if(ans1==0) {
			ans1=x1;
			ans2=x2;
			continue;
		}
		long long tmp=max(ans1/x1,ans2/x2);
		if(tmp*x1<ans1||tmp*x2<ans2)
			tmp++;
		ans1=tmp*x1,ans2=tmp*x2;
	}
	printf("%lld\n",ans1+ans2);
	return 0;
}

Measured memory_bytes: 128
#define STOPIT
#include<bits/stdc++.h>
#define rep(i,n,m) for(int i = (n); i <(m); i++)
#define rrep(i,n,m) for(int i = (n) - 1; i >=(m); i--)
using namespace std;
using ll = long long;

void debug_impl() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_impl(Head head, Tail... tail) { cerr << " " << head; debug_impl(tail...); }
#ifndef STOPIT
    #define debug(...)\
    do {\
        cerr << boolalpha << "[" << #__VA_ARGS__ << "]:";\
        debug_impl(__VA_ARGS__);\
        cerr << std::noboolalpha;\
    } while (false)
#else
    #define debug(...) {}
#endif

template < typename Container, typename Value = typename Container::value_type, enable_if_t<!is_same< Container, string >::value, nullptr_t> = nullptr>
istream& operator>> (istream& is, Container& v)
  { for (auto & x : v) { is >> x; } return is; }

template < typename Container, typename Value = typename Container::value_type, enable_if_t<!is_same< Container, string >::value, nullptr_t> = nullptr >
ostream& operator<< (ostream& os, Container const& v) {
  os << "{";
  for (auto it = v.begin(); it != v.end(); it++)
    {os << (it != v.begin() ? "," : "") << *it;}
  return os << "}";
}
const ll INF = 100000000000000000;


void update_dp(
    int y1, int x1, int y2, int x2, 
    vector<vector<ll>> &dp, 
    const vector<vector<int>> &minmax,
    const vector<ll> &values)
{
  int require = minmax[y2][x2];
  int now = minmax[y1][x1];
  // initial point
  if (x1<0)
  {
    if (require == 1)
      dp[y2][x2] = max(dp[y2][x2], values[x2]);
    return;
  }

  if (require == now)
  {
    dp[y2][x2] = max(dp[y2][x2], dp[y1][x1]);
    return;
  }
  if (require - now >1)
    return;
  
  if (x2-x1==1) return;
  dp[y2][x2] = max(dp[y2][x2], dp[y1][x1]+values[x2]);
}

void solve(vector<ll> values, int n)
{
  // min/ max counts 
  vector<vector<int>> minmax(2, vector<int>(n, 0));
  rep(i, 0, n)
  {
    // min
    minmax[0][i] = n/2 - (n-i-1)/2;
    // max
    minmax[1][i] = (i+2)/2;
  }
  debug(minmax);

  // dynamic programming
  vector<vector<ll>> dp(2, vector<ll>(n, -INF));
  ll res = -INF;
  dp[1][0] = values[0];
  rep(i, 0, n)
  {
    rep(j, 1, 4)
      rep(k, 0, 2)
      {
        update_dp(k, i-j, 0, i, dp, minmax, values);
        update_dp(k, i-j, 1, i, dp, minmax, values);
      }
    debug(i, dp[0][i], dp[1][i]);

    if (minmax[0][i] == n/2)
      res = max(res, dp[0][i]);
    if (minmax[1][i] == n/2)
      res = max(res, dp[1][i]);
  }
  cout << res << endl;
}

int main()
{
  int n;
  cin >> n;
  vector<ll> values(n);
  rep(i, 0, n) cin >> values[i];

  solve(values, n);
  return 0;
}


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

using namespace std;

typedef long long lli;
typedef vector<lli> vll;
typedef vector<bool> vbl;
typedef vector<vector<lli>> mat;

lli a,b,c,d,e,f;
lli den = 1;
lli num = 0;
int main(){
  cin >> a >> b >> c >> d >> e >> f;
  den = 100*a;
  for(lli i = 0;i*a*100 <= f;i++){
    for(lli j = 0;i*a*100+j*b*100 <= f;j++){
      for(lli k = 0;i*a*100+j*b*100+k*c <= f;k++){
        for(lli l = 0;i*a*100+j*b*100+k*c+l*d <= f;l++){
          if((k*c+l*d) <= e*(i*a+j*b)){
            if(num*(i*a*100+j*b*100+k*c+l*d) < (k*c+l*d)*den){
              num = k*c+l*d;
              den = i*a*100+j*b*100+k*c+l*d;
            }
          }
        }
      }
    }
  }
  cout << den << " " << num << endl;
  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;
import java.util.Arrays;

public class Main {

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

    void solve() {
        Scanner sc = new Scanner(System.in);
        int D = sc.nextInt();
        int N = sc.nextInt();
        int c = 0;
        for (int i = 1; i < 10000000; i++) {
            if (i % (int) Math.pow(100, D) == 0 && i % (int) Math.pow(100, D + 1) != 0) {
                c++;
            }
            if (c == N) {
                System.out.println(i);
                return;
            }
        }
    }
}

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

int count[100099];
int red[100099];

int main() {
	// your code goes here
	
	int x,y,n,m;cin>>n>>m;
	for(int i=0;i<n;i++) count[i] = 1;
	red[0] = 1;
	while(m--) {
		cin>>x>>y;
		x = x-1;
		y = y-1;
		
		count[x] -= 1;
		count[y] += 1;
		
		if(red[x]) {
			red[y] = 1;
			if(count[x] == 0) red[x] = 0;
		}
	}
	
	int sum = 0;
	for(int i=0;i<n;i++) sum += red[i]; cout<<sum;
	
	return 0;
}

Measured memory_bytes: 1024
"use strict"
const create = () => {
    const input = require("fs").readFileSync("/dev/stdin", "utf8").trim().split("\n");
    const res = {
        "list": input, "index": 0, "max": input.length,
        "hasNext": function() {return this.index < this.max},
        "next": function() { if (!this.hasNext()) {throw "ArrayIndexOutOfBoundsException";}else{return this.list[this.index++];}}
    };
    return res;
}
const o = create();
const next = () => o.next()
const nextInt = () => parseInt(o.next())
const nextStrArray = () => o.next().split(" ")
const nextIntArray = () => o.next().split(" ").map(el => parseInt(el))
const nextCharArray = () => o.next().split("")
const hasNext = () => o.hasNext()
const myout = (...x) => console.log(...x)
const Main = () => {
    let n = nextInt()
    let a = nextIntArray()
    let b = nextIntArray()
    let ans = 0
    for(let i = 0; i<a.length-1; i++){
        if(a[i] >= b[i]){
            ans += b[i]
        } else if(a[i+1] + a[i] >= b[i]) {
            ans += b[i]
            a[i+1] = a[i+1]-b[i]+a[i]
        } else {
            ans += a[i] + a[i+1]
            a[i+1] = 0
        }
    }
    console.log(ans)
}
Main()



Measured memory_bytes: 50980
import java.util.Scanner

import scala.annotation.tailrec

object Main {
  def main(args: Array[String]): Unit = {
    //nextLineとnextを同時に使ったら死ぬ
    val sc = new Scanner(System.in)

    val n = sc.nextInt()
    val one, two = Vector.fill(n)(sc.nextInt())

    val o = one.scanLeft(0)(_ + _).tail
    val t = two.reverse.scanLeft(0)(_ + _).tail.reverse

    val ans = o.zip(t).map { case (oo, tt) => oo + tt }.max

    println(ans)
  }

  def debug(args: Any*): Unit = {
    Console.err.println(args.mkString(" "))
  }

  def printExecTime(process: => Unit): Unit = {
    val start = System.currentTimeMillis
    process
    debug("処理時間： " + (System.currentTimeMillis - start) + " ミリ秒")
  }

  def bitSearch[T](n: Int, choice: Vector[T]): Vector[Vector[T]] = {
    @tailrec
    def bitSearchLogic(n: Int,
                       choice: Vector[T],
                       acc: Vector[Vector[T]]): Vector[Vector[T]] = {
      if (n == 0) acc
      else {
        val newAcc =
          acc.flatMap(vec => {
            choice.map(c => vec :+ c)
          })
        bitSearchLogic(n - 1, choice, newAcc)
      }
    }

    val firstAcc = choice.map(i => Vector(i))
    bitSearchLogic(n - 1, choice, firstAcc)
  }
}


Measured memory_bytes: 27568
#include <bits/stdc++.h>
#define rep(i, n) for (int i=0; i<(int)(n); i++)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
const ll MOD = 1000000007;
const ll INF = 9999999999;
const int INFI=2147483647;
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;}
template<class T> inline T powerM(T a,T b){if (b==0) return 1;
  T tmp = powerM(a,b/2); if (b%2==0) return tmp*tmp%MOD; else return tmp*tmp%MOD*a%MOD; }


int main() {
  int a,b; cin >>a >>b;
  int res = -1;
  for (int i=1; i<=10000; i++){
    if ((int)((double)i * 0.08) == a && (int)((double)i * 0.1) == b){
      res = i; break;
    }
  }
  cout <<res <<endl;
}

Measured memory_bytes: 256
N, M = map(int, input().split())

l_max = -1
r_min = pow(10, 6)

for i in range(M):
    l, r = map(int, input().split())
    l_max = max(l, l_max)
    r_min = min(r, r_min)

if l_max > r_min:
    print(0)
else:
    print(r_min - l_max + 1)

Measured memory_bytes: 3060
#include <stdio.h>

void insertionSort(int a[],int n){
  int i,j,k,temp;
  for(i=0;i<n;i++){
    temp = a[i];
    j = i-1;
    while(j>=0 && a[j]>temp){
      a[j+1] = a[j];
      j--;
    }
    a[j+1] = temp;
    for(k=0;k<n;k++){
      if(k<n-1){printf("%d ",a[k]);}
      else{printf("%d",a[k]);}
    }
    printf("\n");
  }
}

int main(){
  int i,n,a[100];
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&a[i]);
  }
  insertionSort(a,n);
  return 0;
}

Measured memory_bytes: 604
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;   
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define FOR(i,a,b)  for(int i=a;i<b;++i)
#define RFOR(i,a,b)     for(int i=a;i>=b;--i)
#define init(a, x) memset(a,x,sizeof(a))
#define ld long double
#define dd double
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define all(a) a.begin(),a.end()
#define sz(a) (ll)(a.size())
typedef long long ll;
typedef unsigned long long ull;
typedef pair <ll, ll> pll;
typedef pair <int, int> pii;
typedef vector<pll> vplll;
ll mod = 1e9+7;
const ld PI = 2 * acos(0.0);
const vector<ll> dx = {1, -1, 0, 0};
const vector<ll> dy = {0, 0, 1, -1};
#define round(x, y) ((x + y - 1) / y)
#define ce(x, y) ((x + y - 1) / y)
#define amax(x, y) \
    if (y > x)     \
        x = y;
#define amin(x, y) \
    if (y < x)     \
        x = y;
#define lcm(x, y) ((x) * (y) / __gcd(x, y))
#define len(x) (ll) x.length()
#define sq(x) ((x) * (x))
#define cb(x) ((x) * (x) * (x))
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll a,b,c,t,n,m,k,q; 
    t = 1;
    // cin>>t;
    while(t--)
    {
    	string s;
    	cin>>s;
    	int l = s.length();
    	if(s[l-1]=='s')
    	{
    		s.pb('e');
    	}
    	s.pb('s');
    	cout<<s<<endl;
    }
    return 0;
}

Measured memory_bytes: 3644
#include<bits/stdc++.h>
using namespace std ;
#define rep( i, s, t ) for( register int i = s; i <= t; ++ i )
#define re register
#define int long long 
int gi() {
	char cc = getchar() ; int cn = 0, flus = 1 ;
	while( cc < '0' || cc > '9' ) {  if( cc == '-' ) flus = - flus ; cc = getchar() ; }
	while( cc >= '0' && cc <= '9' )  cn = cn * 10 + cc - '0', cc = getchar() ;
	return cn * flus ;
}
const int P = 1e9 + 7 ; 
const int N = 5000 + 5 ; 
const int M = 3e5 + 5 ;
int A[M], B[M], dp[N][N], fac[N * 4], Ans, n, m ; 
int fpow( int x, int k ) {
	int ans = 1, base = x ; 
	while( k ) {
		if( k & 1 ) ans = ( ans * base ) % P ;
		base = ( base * base ) % P, k >>= 1 ;
	} return ans ; 
}
int C( int x, int y ) {
	return ( fac[y] * fpow( fac[x], P - 2 ) % P ) * fpow( fac[y - x], P - 2 ) % P ;
}
signed main()
{
	n = gi(), m = 2001 ; int inv2 = fpow( 2, P - 2 ) ;
	rep( i, 1, n ) A[i] = gi(), B[i] = gi(), ++ dp[m - A[i]][m - B[i]] ;
	rep( i, 1, 2 * m ) rep( j, 1, 2 * m ) {
		dp[i][j] += ( dp[i - 1][j] + dp[i][j - 1] ) % P, dp[i][j] %= P ; 
	} fac[0] = 1 ; 
	rep( i, 1, 4 * m ) fac[i] = ( fac[i - 1] * i ) % P ;
	rep( i, 1, n ) Ans += dp[m + A[i]][m + B[i]], Ans %= P ;
	rep( i, 1, n ) Ans -= C( 2 * A[i], ( A[i] + B[i] ) * 2 ), Ans = ( Ans + P ) % P ;
	printf("%lld\n", ( Ans * inv2 ) % P ) ;
	return 0 ;
}


Measured memory_bytes: 162816
#include <stdio.h>
#include <string.h>

int main() {
    int k; char str[100];
    scanf("%d", &k);
    scanf("%s", str);

    int sLen = strlen(str);
    if(sLen > k) {
        for(int i = 0; i < k; i++) {
            printf("%c", str[i]);
        }
        printf("...\n");
    } else {
        printf("%s", str);
    }

    return 0;
}

Measured memory_bytes: 1708
#include <iostream>
#include <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;
#define REP(i, j) for(int i = 0; i < j; ++i)
#define FOR(i, j, k) for(int i = j; i < k; ++i)
#define P pair<int, int>

vector<int> check(int n, vector<int> v){
  vector<int> ret(n);
  REP(i, n){
    int cnt = 0;
    REP(j, n) if(v[i] == v[j]) cnt++;
    ret[i] = cnt;
  }
  return ret;
}

int main() {
  int n;
  while(cin >> n && n){
    vector<int> v(n);
    REP(i, n) cin >>v[i];
    int cnt = 0;
    vector<int> next = check(n, v);
    while(v != next){
      cnt++;
      v = next;
      next = check(n, v);
    }
    cout <<cnt <<endl;
    stringstream ss;
    ss << v[0];
    FOR(i, 1, v.size()) ss <<" " <<v[i];
    cout <<ss.str() <<endl;
  }
  return 0;
}

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

#define fi first
#define se second
#define all(v) v.begin(), v.end()
#define sz size()
#define endl "\n"
#define pb push_back
#define pp pop_back
#define mp make_pair
#define REP(I,n) for(int I = 0; I < n; I++)
#define REP_1(I,n) for(int I = 1; I <= n; I++)
#define w(t) int t; cin>>t; while(t--)

#define MOD 1000000007
#define INF 1e9 + 7

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<string> vs;
typedef map<int,int> mii;
typedef map<string,int> msi;
typedef map<int,string> mis;
typedef set<int> si;
typedef set<string> ss;

typedef long long ll;

template<class T>
istream &operator>>(istream &in,vector<T> &arr) {
	for(auto &x : arr)
		in>>x;
	return in;
}

bool sortbylen(string a,string b) {
	return a.length() < b.length();
}
void solve() {
	int n;
	cin>>n;
	set<string> s;
	REP(i,n) {
		string value;
		cin>>value;
		s.insert(value);
	}
	cout<<s.size()<<endl;
}
int main() {
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL); 
	solve();
}

Measured memory_bytes: 19240
while 1:
  n=int(input())
  if not n:break
  f=1
  L={}
  for a,b,c in [input().split() for i in range(n)]:
    if a in L:
      if L[a]>=1e6:continue
      L[a]+=int(b)*int(c)
    else:L[a]=int(b)*int(c)
    if L[a] >= 1e6:print(a);f=0
  if f:print('NA')

Measured memory_bytes: 8260
#include<iostream>
using namespace std;
int main()
{
    int x,y,z,s;
    cin>>x>>y>>z;
    s=x;
    x=y;
    y=s;
    s=x;
    x=z;
    z=s;
    cout<<x<<" "<<y<<" "<<z;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,w;
    cin>>n>>w;
    long long int dp[w+1][n+1]={ 0 },wei[n+1],val[n+1];
    for(int i=1;i<=n;i++)
    {
        cin>>wei[i]>>val[i];
    }
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=w;j++)
        {
            if(i==0||j==0)
            {
                dp[j][i]=0;
            }
            else
            {   
                 dp[j][i]=dp[j][i-1];
                 if(j-wei[i]>=0)
                 {
                     dp[j][i]=max(dp[j][i],val[i]+dp[j-wei[i]][i-1]);
                 }
            }
            
        }
    }
    cout<<dp[w][n];
}

Measured memory_bytes: 79104
N = int(input())
for h in range(1, 3501):
    for n in range(1, 3501):
        numera = 4 * h * n - n * N - h * N
        denomi = h * n * N
        if numera <= 0:
            continue
        elif denomi % numera != 0:
            continue
        w = denomi // numera
        print(h, n, w)
        exit()

Measured memory_bytes: 67812
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

void a()
{
   int X, t;
    cin >> X >> t;
    if(X <= t)
    {
        cout << 0 << endl;
    }else{

        cout << X - t << endl;
    }
}

void b()
{
    string s;
    cin >> s;
    for(int i = 0; i < s.size(); i++)
    {
        if ((i % 2) == 0)
        {
            cout << s[i];
        }
    }
    cout << endl;
}

void c()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    vector<int> v(100000, 0);
    for(auto e : a)
    {
        v[e]++;
    }
    int resut = v[0] + v[1];
    for(int i = 1; i < 100000 - 1; i++)
    {
        int temp = v[i - 1] + v[i] + v[i + 1];
        if (resut < temp) resut = temp;
    }
    cout << resut << endl;


}

void d()
{
    int n;
    cin >> n;
    vector<int> p(n);
    for(int i = 0; i < n; i++)
    {
        cin >> p[i];
    }
    int count = 0;
    for(int i = 0; i < n - 1; i++)
    {
        if(p[i] == i + 1)
        {
            int temp = p[i];
            p[i] = p[i + 1];
            p[i + 1] = temp;
            count++;
        }
    }
    if(p[n - 1] == n) count++;
    cout << count << endl;
}

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


Measured memory_bytes: 640
#include <cstdio>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <map>
#include <set>

#define MIN_INT -2147483648
#define MAX_INT 2147483647
#define MIN_LONG -9223372036854775808L
#define MAX_LONG 9223372036854775807L
#define PI 3.141592653589793238462643383279502884L

#define long long long int

using std::vector;
using std::map;
using std::set;
using std::string;
using std::pair;
using std::cin;
using std::cout;
using std::cerr;

// @author: pashka

vector<long> x;
vector<long> y;
int s = 0;

int main() {
    std::ios::sync_with_stdio(false);

    int n;
    cin >> n;
    x.resize(n);
    y.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> x[i] >> y[i];
    }
    for (int i = 0; i < n; i++) {
        if (x[i] < x[s] || x[i] == x[s] && y[i] < y[s]) {
            s = i;
        }
    }
    vector<int> p;
    for (int i = 0; i < n; i++) {
        if (i != s) {
            p.push_back(i);
        }
    }
    std::sort(p.begin(), p.end(), [](const int & a, const int & b) -> bool {
        long vp = (x[a] - x[s]) * (y[b] - y[s]) - (x[b] - x[s]) * (y[a] - y[s]);
        if (vp != 0) return vp > 0;
        long da = (x[a] - x[s]) * (x[a] - x[s]) + (y[a] - y[s]) * (y[a] - y[s]);
        long db = (x[b] - x[s]) * (x[b] - x[s]) + (y[b] - y[s]) * (y[b] - y[s]);
        return da < db;
    });

    vector<int> st;
    st.push_back(s);
    for (int v : p) {
//        cout << x[v] << " " << y[v]<< "\n";
        while (st.size() >= 2) {
            int a = st[st.size() - 1];
            int b = st[st.size() - 2];
            long x1 = x[a] - x[b];
            long y1 = y[a] - y[b];
            long x2 = x[v] - x[a];
            long y2 = y[v] - y[a];
            long vp = x1 * y2 - x2 * y1;
            if (vp <= 0) {
                st.pop_back();
            } else {
                break;
            }
        }
        st.push_back(v);
    }
    vector<double> res(n);
    for (int i = 0; i < st.size(); i++) {
        int a = st[i];
        int v = st[(i + 1) % st.size()];
        int b = st[(i + 2) % st.size()];
        long x1 = x[a] - x[v];
        long y1 = y[a] - y[v];
        long x2 = x[b] - x[v];
        long y2 = y[b] - y[v];
        long vp = x1 * y2 - x2 * y1;
        long sp = x1 * x2 + y1 * y2;
        double an = atan2(vp, sp);
        res[v] = (PI + an) / (2 * PI);
    }
    cout << std::setprecision(20);
    for (int i = 0; i < n; i++) {
        cout << res[i] << "\n";
    }

    return 0;
}

Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
int zero;
void match(string a, string b, vector<bool> &ab){
// ofstream ofs("a.txt");
// if(!ofs){
//     cout<<"file open error"<<endl;
//     cin.get();
//     return;
// }
    int A=a.size();
    int B=b.size();
    for(int i=-B+1; i<A; i++){
        int a_start=max(0,i);
        int a_end=min(A-1,i+B-1);
        int b_start=max(-i,0);
        for (int j = 0; j <= a_end-a_start; j++){
// ofs<<i<<" "<<j<<endl;
           char c=a[a_start+j];
           char d=b[b_start+j];
           if(c!='?'&&d!='?'&&c!=d){
               ab[zero+i]=false;
               break;
           } 
        }
    }
}
int main() {
    string a,b,c;
    cin>>a>>b>>c;
    int A=a.size();
    int B=b.size();
    int C=c.size();
// cout<<A<<" "<<B<<" "<<C<<endl;
    zero=2*(A+B+C);
    vector<bool> ab(2*zero,true);
    vector<bool> ac(2*zero,true);
    vector<bool> bc(2*zero,true);
    match(a,b,ab);
    match(a,c,ac);
    match(b,c,bc);
    int ans=10000;
    for(int i=-B-C;i<=A+C;i++){
        for (int j = -B-C; j <=A+B; j++){
            if(ab[zero+i]&&ac[zero+j]&&bc[zero+j-i])
                ans=min(ans,max(max(i+B,j+C),A)-min(min(i,j),0));
        }
    }
    cout << ans<<endl;
}

Measured memory_bytes: 384
#include<iostream>
#include<string>
#include<iomanip>
#include<cmath>
#include<vector>
#include<algorithm>

using namespace std;

#define int long long
#define rep(i,n) for(int i = 0; i < (n); i++)
#define INF ((long long)1e18)
#define MOD ((int)1e9+7)
#define endl "\n"

#define yn(f) ((f)?"Yes":"No")
#define YN(f) ((f)?"YES":"NO")

#define MAX 100001

int s[MAX], t[MAX], ans[MAX];
pair<int,int> x[MAX];

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	int A, B, Q, a, b, c, d;
	
	cin>>A>>B>>Q;
	
	rep(i,A)cin>>s[i];
	rep(i,B)cin>>t[i];
	rep(i,Q){
		cin>>x[i].first;
		x[i].second = i;
	}
	
	sort(x,x+Q);
	
	for(int i = 0, j = 0, k = 0; i < Q; i++){
		for(;j < A && x[i].first >= s[j];j++);
		for(;k < B && x[i].first >= t[k];k++);
		a = j?x[i].first-s[j-1]:INF;
		b = j-A?s[j]-x[i].first:INF;
		c = k?x[i].first-t[k-1]:INF;
		d = k-B?t[k]-x[i].first:INF;
		ans[x[i].second] = min(min(max(a,c),max(b,d)),min(min(a,d)*2+max(a,d),min(b,c)*2 + max(b,c)));
	}
	
	for(int i = 0; i < Q; i++) cout<<ans[i]<<endl;
	
	return 0;
}

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

typedef long long ll;

ll N, K;

void solve() {
  ll base = (N - 1) * (N - 2) / 2;
  if (base < K) {
    cout << -1 << endl;
    return;
  }
  ll diff = base - K;
  vector<pair<ll, ll>> edges;
  for (ll i = 1; i < N; ++i) edges.push_back(make_pair(0, i));
  for (ll i = 1; i < N; ++i) {
    if (diff == 0) break;
    for (ll j = i + 1; j < N; ++j) {
      if (diff == 0) break;
      edges.push_back(make_pair(i, j));
      --diff;
    }
  }
  cout << edges.size() << endl;
  for (auto edge : edges) {
    ll u = edge.first + 1, v = edge.second + 1;
    cout << u << " " << v << endl;
  }
}
int main() {
  cin >> N >> K;
  solve();
  return 0;
}


Measured memory_bytes: 512
#include<iostream>
#include<string>
#include<array>
#include<algorithm>
#include<deque>
#include<vector>

int main(void) {
	int N, T;
	int c, t;
	int result = 12345;
	std::cin >> N >> T;
	for (int i = 0; i < N; i++) {
		std::cin >> c >> t;
		if (t <= T) {
			if (c < result) {
				result = c;
			}
		}
	}
	if (result == 12345) {
		std::cout << "TLE" << std::endl;
	}
	else{
		std::cout << result << std::endl;
	}
}

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

#define rep(i,k,n) for(int (i)=(k);(i)<(n);(i)++)
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define abs(a) ((a)>0 ?(a):-(a))
#define llong long long

int main(){
	llong f[10000001]={0,1,2};
	llong p[5000001]={2};	// 素数列
	int p_num=1;	// 見つかった素数の数
	int N; scanf("%d",&N);
	if( N==1 ){ printf("1"); return 0; }
	if( N==2 ){ printf("5"); return 0; }
	N++;
	rep(i,3,N) f[i]=1;
	llong ans=5;
	rep(i,3,N){
		int k=i;
		int i_2 = sqrt(i)+1;
		rep(j,0,p_num){
			if( p[j]>i_2 ) break;
			if( k%p[j]==0 ){
				int cnt=1;
				while( k%p[j]==0 ){
					cnt++;
					k /= p[j];
				}
				f[i] = cnt*f[k];
				break;
			}
		}
		if( f[i]==1 ){
			f[i]=2;
			if( i*i<N ){
				p[p_num]=i; p_num++;
			}
		}
		ans += i*f[i];
	}
	printf("%lld",ans);
	return 0;
}



Measured memory_bytes: 119336