akhauriyash/Code-Regression huggingface dataset:
/*
	Name:
	Author: xiaruize
	Date:
*/

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define MOD 1000000007
#define ALL(a) (a).begin(), (a).end()
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define ll long long
#define form(i,j,n) for(int i=int(j);i<=int(n);i++)
#define pb push_back
#define mk make_pair
#define pii pair<int,int>
#define pis pair<int,string>
#define sec second

inline int read()
{
    char ch=getchar();
    int x=0,f=1;
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    return x*f;
}

int main()
{
 	ios::sync_with_stdio(false);
	cin.tie(0);
 	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	long double l;
	cin>>l;
	cout<<fixed<<setprecision(12)<<(l/3*1.0)*(l/3*1.0)*(l/3*1.0)<<endl;
	return 0;
}

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

s = 0
X = [0] * N
for i in range(N):
    x, w = map(int, input().split())
    x += ((w + 1) % 3 - 1) * T
    # xが0点を通る回数を足す
    s += x // L
    X[i] = x % L

X.sort()
for i in range(N):
    print(X[(i+s) % N])


Measured memory_bytes: 8116
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int m = scanner.nextInt();
		int l = scanner.nextInt();
		int[][] A = new int[n][m];
		int[][] B = new int[m][l];
		long[][] C = new long[n][l];
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				A[i][j] = scanner.nextInt(); 
			}
		}
		for(int i=0;i<m;i++) {
			for(int j=0;j<l;j++) {
				B[i][j] = scanner.nextInt(); 
			}
		}
		
		for(int i=0;i<n;i++) {
			for(int j=0;j<l;j++) {
				long temp = 0;
				for(int k=0;k<m;k++) {
					temp += A[i][k]*B[k][j];
				}
				C[i][j] = temp;
				if (j!=l-1) {
					System.out.print(C[i][j] + " ");
				}else {
					System.out.print(C[i][j]);
				}
			}
			System.out.println();
		}
		scanner.close();
		
	}
}


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

using F = double;

struct Point {F x, y;};
struct Interval {
  F lx, rx;
  int l, r;
  Interval(F lx, F rx, int l, int r) : lx(lx), rx(rx), l(l), r(r) {}
  bool operator<(auto o) const {
    if(lx != o.lx) return lx < o.lx;
    if(rx != o.rx) return rx < o.rx;
    if(l != o.l) return l < o.l;
    return r < o.r;
  }
};

const F PI = acos(-1);
const F INF = 1e9;

int N;
vector<Point> P;

F tune(auto a) {
  while(a  < 0) a += PI;
  while(PI < a) a -= PI;
  return a;
}

F projection(auto p, auto a) {
  return p.x * sin(a) + p.y * cos(a);
}

tuple<F, F, F> coefficient(auto a) {
  vector<pair<F, int>> lx;
  for(auto i = 0; i < P.size(); ++i) lx.emplace_back(projection(P[i], a) - 1, i);
  sort(begin(lx), end(lx));

  vector<pair<int, int>> shadow;
  shadow.emplace_back(lx.front().second, lx.front().second);
  for(auto i: lx) {
    auto rx = projection(P[shadow.back().second], a) + 1;
    if(rx < i.first) shadow.emplace_back(i.second, i.second);
    else             shadow.back().second = i.second;
  }

  F A = 0, B = 0, C = 0;
  for(auto s: shadow) {
    auto l = P[s.first];
    auto r = P[s.second];
    A += r.x - l.x;
    B += r.y - l.y;
    C += 1   - -1;
  }
  return make_tuple(A, B, C);
}

vector<F> solve() {
  vector<F> angle = {0, PI};
  for(auto j = 0; j < N; ++j) for(auto i = 0; i < j; ++i) {
    auto dx = P[i].x - P[j].x;
    auto dy = P[i].y - P[j].y;
    auto d = hypot(dx, dy);
    auto a = atan2(dy, dx);
    angle.emplace_back(tune(-a));
    angle.emplace_back(tune(asin(2 / d)  - a));
    angle.emplace_back(tune(asin(-2 / d) - a));
  }
  sort(begin(angle), end(angle));
  angle.erase(unique(begin(angle), end(angle)), end(angle));

  F a_min = INF, a_max = -INF;
  F s_min = INF, s_max = -INF;
  for(auto i = 1; i < angle.size(); ++i) {
    auto low  = angle[i - 1];
    auto high = angle[i];
    auto middle = (low + high) / 2;

    F a, b, c;
    tie(a, b, c) = coefficient(middle);

    for(auto i: {low, tune(PI / 2 - atan2(b, a))}) if(low <= i && i <= high) {
      auto s = a * sin(i) + b * cos(i) + c;
      if(s_min > s) {
        s_min = s;
        a_min = i;
      }
      if(s_max < s) {
        s_max = s;
        a_max = i;
      }
    }
  }

  return {a_min, a_max};
}

int main() {
  while(cin >> N, N) {
    P = vector<Point>(N);
    for(auto& i: P) cin >> i.x >> i.y;

    for(auto i: solve()) cout << setprecision(15) << fixed << i << endl;
  }
}

Measured memory_bytes: 3808
#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;

int main() {
  long long n;
  cin >> n;
  long long mmin = LONG_MAX;
  for (long long i=0; i<5; i++) {
    long long m;
    cin >> m;
    mmin = min(mmin, m);
  }

  // cout << ceil(n/(long double)mmin)+4 << endl;
  printf("%ld\n", ((long)ceil(n/(long double)mmin)+4));
}

/*
5
3 2 4 3 5
5 4 3 3 2

0 0 0 0 0 6
6

並びでは変わらない．
ボトルネック 2 
*/

Measured memory_bytes: 384
#include<stdio.h>
#include<stdlib.h>
#define N 100

int

main(){
  
  int x[N],i=0;
  char s[N];

  while( scanf("%s", s) != EOF ){
    if ( s[0] == '+' ){
      x[i-2]=x[i-2]+x[i-1];
      i--; 
    } else if ( s[0] == '-' ){
      x[i-2]=x[i-2]-x[i-1];
      i--;
    } else if ( s[0] == '*' ){
      x[i-2]=x[i-2]*x[i-1];
      i--;
    } else {
      x[i] = atoi(s);
      i++;
    }
  }
  printf("%d\n",x[0]);
  return 0;
}

Measured memory_bytes: 548
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define dump(...)
#endif
#define endl '\n'
//#define int long long
#define FOR(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define REP(i, x) for (int i = 0; i < (int)(x); i++)
#define REPS(i, x) for (int i = 1; i <= (int)(x); i++)
#define RREP(i, x) for (int i = ((int)(x)-1); i >= 0; i--)
#define RREPS(i, x) for (int i = ((int)(x)); i > 0; i--)
#define INF 2147483647
#define LLINF 9223372036854775807LL
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define BIT(n) (1LL << (n))
#define TOUPPER(s) transform(s.begin(), s.end(), s.begin(), ::toupper)
#define TOLOWER(s) transform(s.begin(), s.end(), s.begin(), ::tolower)
#define FILLZERO(s, n)                      \
    do {                                    \
        ostringstream os;                   \
        os << setw(n) << setfill('0') << s; \
        s = os.str();                       \
    } while (0);
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end()) //sortしてからつかうこと
#define INIT                               \
    std::cin.tie(nullptr);                 \
    std::ios_base::sync_with_stdio(false); \
    cout << std::fixed << std::setprecision(10);

using ll = long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using pi = pair<int, int>;
template <typename T>
using Pq = priority_queue<T>;
template <typename T>
using pQ = priority_queue<T, vector<T>, greater<T>>;

template <typename T>
vector<T> make_vec(size_t a, T n) { return vector<T>(a, n); }
template <typename T, typename... Ts>
auto make_vec(size_t a, Ts... ts) { return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...)); }
template <class T>
inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return 1;
    }
    return 0;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &vec) {
    for (T &x : vec)
        is >> x;
    return is;
}

constexpr ll MOD = 1e9 + 7;
int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1};
int dy[8] = {0, 1, 0, -1, 1, -1, 1, -1};
ll A, B, C, D, E, F, G, H, N, M, L, K, P, Q, R, W, X, Y, Z;
string S, T;
ll ans = 0;

signed main() {
    INIT;
    cin >> N >> K;
    vi a;
    REP(i, N) {
        cin >> A;
        if (A < K)
            a.push_back(A);
    }
    sort(RALL(a));
    N = a.size();
    vi dp(K + 1);
    dp[0] = 1;
    ans = N;
    REP(i, N) {
        RREP(j, K) {
            if (dp[j]) {
                if (j + a[i] >= K) {
                    ans = N - 1 - i;
                } else {
                    dp[j + a[i]] = 1;
                }
            }
        }
        dump(dp);
    }
    cout << ans << endl;
}

Measured memory_bytes: 3700
#include <stdio.h>

long long int gcd(long long int x, long long int y){
    if(x == y){return x;}
    else if(x > y){return gcd(x-y, y);}
    else{return gcd(x, y-x);}
}

long long int lcm(long long int x, long long int y){
    return x*y/gcd(x, y);
}

int main(void) {
    long long int a, b, c, d, i;
    scanf("%lld %lld %lld %lld", &a, &b, &c, &d);
    long long int x = lcm(c, d);
    long long int ans = (b-(a-1)) - (b/c - (a-1)/c) - (b/d - (a-1)/d) + (b/x - (a-1)/x);
    printf("%lld\n", ans);
    return 0;
}

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


int main() {
  string s,t,u;
  int a,b;
  cin >> s >> t;
  cin >> a >> b;
  cin >> u;
  if (s==u) cout << a-1 << " " << b << endl;
  else cout << a << " " << b-1 << endl;
}


Measured memory_bytes: 256
#include <stdio.h>

int main()
{
 int n,a[1000],i,j,mini,dem=0;
 scanf("%d",&n);
 for(i=0;i<n;i++)
 {
  scanf("%d",&a[i]);
 }
 for (i = 0;i<n;i++)
 {    mini = i;
      for (j = i;j<n;j++)
      {
        if (a[j] < a[mini])
           {
             mini = j;
           }
      }
	  if(i !=mini)
		 {
			 int temp=a[i];
             a[i]=a[mini];
             a[mini]=temp;      
			 dem++;
		}             
 }
 printf("%d",a[0]);
 for(i=1;i<n;i++)
 {
  printf(" %d",a[i]);
 }
 printf("\n%d\n",dem);
 return 0;
}

Measured memory_bytes: 604
#define _USE_MATH_DEFINES
#define INF 10000000
#include <iostream>
#include <sstream>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>
#include <list>

using namespace std;

typedef long long ll;
typedef pair <int,int> P;
typedef pair <P,P> PP;
typedef pair <int,PP> PPP;

static const double eps = 1e-8;

static const int moveTo[][2] = {{1,0},{0,-1},{-1,0},{0,1}};
static const int moveToRev[][2] = {{-1,0},{0,1},{1,0},{0,-1}};

int stage[50][50];
int costTable[50][50][50][50];

int bfs(int tx,int ty,int kx,int ky,int w,int h){
	priority_queue<PPP,vector<PPP>,greater<PPP> > que;
	que.push(PPP(0,PP(P(tx,ty),P(kx,ky))));	
	memset(costTable,0x3,sizeof(costTable));

	int res = INF;
	costTable[tx][ty][kx][ky] = 0;
	while(!que.empty()){
		int cost = que.top().first;
		if(res <= cost || cost >= 100){
			que.pop(); continue;
		}

		int tx = que.top().second.first.first;
		int ty = que.top().second.first.second;
		int kx = que.top().second.second.first;
		int ky = que.top().second.second.second;

		if(tx==kx && ty == ky) res = min(res,cost);

		que.pop();

		for(int i=0;i<4;i++){
			int tdx = tx + moveTo[i][0];
			int tdy = ty + moveTo[i][1];

			if((tdx < 0 || tdx >= w || tdy < 0 || tdy >=h) || stage[tdy][tdx]) {
				tdx = tx;
				tdy = ty;
			}

			int kdx = kx + moveToRev[i][0];
			int kdy = ky + moveToRev[i][1];

			if((kdx < 0 || kdx >= w || kdy < 0 || kdy >=h) || stage[kdy][kdx]) {
				kdx = kx;
				kdy = ky;
			}
			if(costTable[tdx][tdy][kdx][kdy] <= cost + 1) continue;
			costTable[tdx][tdy][kdx][kdy] = cost + 1;
			que.push(PPP(cost+1,PP(P(tdx,tdy),P(kdx,kdy))));
		}
	}

	return res;
}

int main(){

	int w,h;
	while(~scanf("%d %d",&w,&h)){
		if(w == h && h==0) break;
		int tx,ty;
		scanf("%d %d",&tx,&ty);
		int kx,ky;
		scanf("%d %d",&kx,&ky);
		for(int y=0;y<h;y++){
			for(int x=0;x<w;x++){
				scanf("%d",&stage[y][x]);
			}
		}

		int res = bfs(tx-1,ty-1,kx-1,ky-1,w,h);
		if(res >= 100) printf("NA\n");
		else printf("%d\n",res);
	}
}

Measured memory_bytes: 25000
# coding: utf-8
import itertools
import math
import bisect

class Node:
    def __init__(self, id, next, rest):
        self.id = id
        self.before = None
        self.next = next
        self.rest = rest
        self.d = None
        self.f = None

    def update_next(self):
        self.next = first(self.rest)
        self.rest = rest(self.rest)


N = int(input())
graph = []
for _ in range(N):
    l = list(map(int, input().split(" ")))
    id = l[0]
    if l[1] != 0:
        next = l[2]
    else:
        next = None
    if l[1] >= 2:
        rest = l[3:]
    else:
        rest = []
    graph.append(Node(l[0], next, rest))

def first(l):
    if l==None:
        return None
    if len(l) == 0:
        return None
    else:
        return l[0]

def rest(l):
    if l == None:
        return None
    if len(l) >= 2:
        return l[1:]
    else:
        return None

def dfs(graph):
    stack = [graph[0]]
    stack[-1].d = 1
    tansakuzumi = [1]
    mitansaku = list(range(1, len(graph)+1))
    res_graph = []
    t = 2
    while len(stack) != 0:
        tansakuzumi.append(stack[-1].id)
        if stack[-1].id in mitansaku:
            mitansaku.remove(stack[-1].id)
        if stack[-1].next == None:
            stack[-1].f = t
            res_graph.append(stack.pop())
            t += 1
        elif stack[-1].next in tansakuzumi:
            stack[-1].update_next()
        else:
            stack.append(graph[stack[-1].next-1])
            stack[-2].update_next()
            stack[-1].d = t
            t += 1
        if len(stack) == 0 and len(mitansaku) >= 1:
            stack.append(graph[mitansaku[0]-1])
            stack[-1].d = t
            t += 1
    return res_graph




res_graph = dfs(graph)

res_graph.sort(key=lambda x: x.id)

for n in res_graph:
    print("{} {} {}".format(n.id, n.d, n.f))



Measured memory_bytes: 5776
#include <stdio.h>

int main (void) 
{
    int n,x,t;
    int ans;

    scanf("%d %d %d", &n, &x, &t);

    if (n/x < 1) { 
        ans = t;
    }
    else {
        ans = n / x * t;
        if (n%x != 0) {
            ans+=t;
        }
    }
    printf("%d", ans);
    return 0;
}

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

int cmp( const void *p, const void *q ) {
    return *(int*)p - *(int*)q;
}

int main(void)
{ 
  int n, k, i;
  int length = 0;
  int array[100];
  
  scanf("%d%d", &n, &k);
  for (i = 0; i < n; i++) 
    scanf("%d", &array[i]);
  qsort(array, n, sizeof(int),cmp);
  
  for (i = n -1; k-- > 0; i--)
    length += array[i];
  
  printf("%d", length);
  return 0;
}
  
  
  
  

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define maxn int(1e5+5)
using namespace std;

int arr[maxn], n;
int best[2];
int val = -1;
int cnt(int i,bool flag=false){
    map<int,int> mp;
    for(;i<n;i+=2){
        mp[arr[i]]++;
    }
    int mx=0, total=0;
    for(auto p:mp){
        total+=p.second;
        if(p.second>mx && (!flag || p.first!=val)){
            mx = p.second;
            if(flag==false) 
                val = p.first;
        }
    }
    return total-mx;
}

int main(){
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> arr[i];
    }
    cout << min(cnt(0)+cnt(1,true),cnt(1)+cnt(0,true)) <<'\n';
    return 0;
}

Measured memory_bytes: 6240
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>
int acs(const void *a, const void *b){return *(int*)a - *(int*)b;} /* 1,2,3,4.. */
int des(const void *a, const void *b){return *(int*)b - *(int*)a;} /* 8,7,6,5.. */
int cmp_char(const void *a, const void *b){return *(char*)a - *(char*)b;} /* a,b,c,d.. */
int cmp_str(const void *a, const void *b){return strcmp(*(const char **)a, *(const char **)b);} /* aaa,aab.. */
#define min(a,b) (a < b ? a: b)
#define max(a,b) (a > b ? a: b)
#define rep(i, l, r) for (int i = l; i < r; i++)
#define MAX 100001
#define MOD 1000000007

typedef long long int lli;

int main(void) {
  int n, k, r, s, p;
  char t[100001];
  scanf("%d %d %d %d %d %s", &n, &k, &r, &s, &p, t);

  int ans = 0;
  for (int ki = 0; ki < k; ki++) { // k番目までのジャンケンスタート
    char prev = 'a';
    for (int ni = ki; ni < n; ni += k) {
      char hand = t[ni];
      if (hand == prev) {
        prev = 'a';
        continue;
      }
      if (hand == 'r') {
        ans += p;
      } else if (hand == 's') {
        ans += r;
      } else if (hand == 'p') {
        ans += s;
      } 
      prev = hand;
    }
  }
  printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        int a = sc.nextInt();
        int b = sc.nextInt();
        sc.close();

        x -= a;

        System.out.println(x % b);
    }
}


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

long long int gcd(long long int a, long long int b) {
    if (a < 0) a = -a;
    if (b < 0) b = -b;
    
    if (b == 0) return a;
    else return gcd(b, a % b);
}

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

    long long int ans = 0;
    for(int a=1; a<=k; a++){
        for(int b=1; b<=k; b++){
            for(int c=1; c<=k; c++){
                ans += gcd(gcd(a,b), c);
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3636
#include<bits/stdc++.h>
#include<iostream>
#include <cmath>    

using namespace std;
int combine(int a, int b) {
   int times = 1;
   while (times <= b)
      times *= 10;
   return a*times + b;
} 
int main(){
	ios_base::sync_with_stdio(false); //Fast I/O
	cin.tie(NULL);
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);	
	int a,b;
	cin >> a >> b;
	
	int res;
	res=combine(a,b);
	
	double A=sqrt(res);
	int i=A;
	
	if(A==i)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
	
	return 0;
}


Measured memory_bytes: 256
a = int(input())
b = int(input())
c = int(input())
x = int(input())

count = 0

for i_a in range(a + 1):
  for i_b in range(b + 1):
    for i_c in range(c + 1):
      if 500*i_a + 100*i_b + 50*i_c == x:
        count += 1
        
print(count)

Measured memory_bytes: 3060
#include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<cstdlib>
    #include<algorithm>
    #include<map>
    #include<cmath>
    #include<cstdlib>
    using namespace std;
    const int M=200005;
long long int a,b,c,u,a1;
int main()
{
    cin>>a>>b>>c;
    int flag=0;
    for(int i=1;i<=100;i++)
    {
        a1=a;
        a1=a*i;
        u=a1%b;
        if(u==c)
        {
            flag=1;
            break;
        }
    }
    if(flag==0)
        cout<<"NO"<<endl;
    else if(flag==1)
        cout<<"YES"<<endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<queue>
#include<deque>
#include<vector>
#include<math.h>
#include<iomanip>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<set>
#include<map>
#include<bitset>
#include<unordered_set>
#include<unordered_map>
 
#define pi 3.141592653
#define in freopen("entrada","r",stdin);
#define out freopen("myfile.txt","w",stdout);
#define ii pair<int,int> 
#define fast_io cin.tie(0), cin.sync_with_stdio(false);
#define inf 0x3f3f3f3f
#define sup_inf 1e18
#define f first
#define s second
#define eps 1e-9

#define nl ( no << 1)
#define nr ( no << 1)|1
#define mid l+(( r-l)>>1)
 
using namespace std;
typedef long long ll;	
typedef long double ld;
typedef unsigned long long ull;
typedef  pair< long long , pair< int,int> > iii;

const int maxn = 2e5 + 100; 
const int MAX = 1010;
const int mod = 1e9 + 7;
const int MAXLV = 16;
 

using namespace std;



int an[maxn], sz[maxn];


int n, m , ans = 1;


int findc(int u ){
  while ( an[u] != u ){
    u = an[u] = an[an[u]];
  }
  return u;
}

void une ( int a, int b) { 
  
  int x = findc(a);
  int y = findc(b);
  if ( x == y) return;
  an[x] = y;
  sz[y]+=sz[x];
  ans = max ( sz[y], ans );
}



int main () { 
  
  
  //~ in
  fast_io
  cin >> n >> m;
  
  for(int i = 0 ;i < maxn;i++) { 
    an[i] = i;
    sz[i] = 1;
  }
  
  for(int i = 0 ;i < m;i++ ){ 
    int ai, bi;
    cin >> ai >> bi;
    une ( ai, bi);
  }
  
  
  
  cout << ans << '\n';
  
  
  
  return 0;
}


Measured memory_bytes: 4752
#include <stdio.h>
//#include <stdlib.h>
//#include <string.h>
//#include <stdbool.h>
//#include <limits.h>
//#include <math.h>

int main() {
  long a, b, k;
  scanf("%ld %ld %ld", &a, &b, &k);
  if (a+b < k)
    printf("0 0\n");
  else if (a < k)
    printf("0 %ld\n", a+b-k);
  else
    printf("%ld %ld\n", a-k, b);
  return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <string>
#include <sstream>
#include <algorithm>
#include <random>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#include <cassert>
#include <climits>
#include <bitset>
#include <functional>

#define FOR_LT(i, beg, end) for (int i = beg; i < end; i++)
#define FOR_LE(i, beg, end) for (int i = beg; i <= end; i++)
#define FOR_DW(i, beg, end) for (int i = beg; end <= i; i--)

using namespace std;

static const int64_t kRem = 1000003;

int64_t pow_rem(int64_t x, int64_t m, int64_t rem)
{
	if (m == 1) {
		return x;
	}

	if (m & 1) {
		int64_t val = pow_rem(x, m / 2, rem);
		val = val * val;
		val %= rem;
		val *= x;
		val %= rem;
		return val;
	}
	else {
		int64_t val = pow_rem(x, m / 2, rem);
		val = val * val;
		val %= rem;
		return val;
	}
}
tuple<int64_t, int64_t, int64_t> gcd(int64_t x, int64_t y)
{
	assert(0 < x);
	assert(0 <= y);

	if (x < y) swap(x, y);

	if (y == 0) return make_tuple(x, 1, 0);

	tuple<int64_t, int64_t, int64_t> ret = gcd(y, x % y);

	return make_tuple(get<0>(ret), get<2>(ret), get<1>(ret) - (x / y) * get<2>(ret));
}

int64_t divide_rem(int64_t divident, int64_t dividor, int64_t rem)
{
	int64_t ret = get<2>(gcd(rem, dividor));
	while (ret < 0) ret += rem;

	ret *= divident;
	ret %= rem;

	return ret;
}

int64_t table[kRem + 1] = { 0 };

void make_table()
{
	int64_t val = 1;
	FOR_LE(i, 1, kRem) {
		val *= i;
		val %= kRem;
		table[i] = val;
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	make_table();

	int qnum; cin >> qnum;
	FOR_LT(q, 0, qnum) {
		int64_t x, d, n; cin >> x >> d >> n;

		if (d == 0) {
			cout << pow_rem(x, n, kRem) << endl;
			continue;
		}

		int64_t val = pow_rem(d, n, kRem);
		int64_t s = divide_rem(x, d, kRem);
		if (kRem <= s + n - 1) {
			cout << 0 << endl;
			continue;
		}

		val *= table[s + n - 1];
		val %= kRem;
		val = divide_rem(val, table[s - 1], kRem);

		cout << val << endl;
	}

	return 0;
}

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

int main(){
 int a,b,d,r;
 double f;

 cin >> a >> b;
 d=a/b;
 r=a%b;
 f=(double)a/b;

 cout << d << " " << r << " " << fixed << f << endl;

 return 0;
}

Measured memory_bytes: 3192
//(N * h * n)/(4 * h * n - N * n - N * h)

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

double val(double h, double n)
{
	double upper=N*h*n;
	double lower=(4*h*n - N*n - N*h);
	
	return upper/lower;
	
}

int main()
{
	cin>>N;
	for(long long i=1;i<=3500;i++)
	{
		for(long long j=1;j<=3500;j++)
		{
			double k=val((double)i,(double)j);
			long long k2=k;
			if(k==k2 and k>0)
			{
				cout<<i<<" "<<j<<" "<<k2;
				return 0;
			}
		}
	}
	
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define dunk(a) cout << (a) << endl
#define rall(a) (a).rbegin(),(a).rend()
const int INF = 2e9;
using namespace std;
using Graph = vector<vector<int>>;
typedef pair<int,int> P;
typedef long long ll;

int main(){
    ll n, m; cin >> n >> m;
    if(n*2 <= m){
        cout << n + (m-n*2)/4 << endl;
    }
    else{
        cout << min(n,m/2) << endl;
    }
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp20
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] input = Console.ReadLine().Split(' ');
            string one = input[0].ToUpper();
            string two = input[1].ToUpper();
            string thr = input[2].ToUpper();

            Console.WriteLine($"{one[0]}{two[0]}{ thr[0]}");
                Console.Read();
        }
    }
}


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

using namespace std;

#define FOR(i, j, k, in) for (int i = j; i < k; i += in)
#define RFOR(i, j, k, in) for (int i = j; i >= k; i -= in)
#define REP(i, j) FOR(i, 0, j, 1)
#define FOREACH(it, l) for (auto it = l.begin(); it != l.end(); it++)
#define MP make_pair
#define PB push_back
#define PI 3.1415926535897932384626433832795
#define MOD 1000000007
const double pi = acos(-1.0);
typedef pair<int, int> PII;
typedef long int int32;
typedef unsigned long int uint32;
typedef long long int int64;
typedef unsigned long long int uint64;

#define int long long
#define trace(x) cerr << #x << ": " << x << " " << endl;

inline int add(int a, int b)
{
    a += b;
    if (a >= MOD)
        a -= MOD;
    return a;
}
inline int sub(int a, int b)
{
    a -= b;
    if (a < 0)
        a += MOD;
    return a;
}
inline int mul(int a, int b) { return (int)((int)a * b % MOD); }

#define IOS                           \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);

int dsum(int i)
{
    int ct = 0;
    while (i > 0)
    {
        ct += i % 10;
        i = i / 10;
    }
    return ct;
}

signed main()
{
    IOS
        string s;
    cin >> s;
    int d;
    cin >> d;
    // reverse(s.begin(), s.end());
    vector<vector<int>> dp(d, vector<int>(2, 0)); //1 is smaller_already 0 is not smaller yet
    dp[0][0] = 1;
    REP(i, s.size())
    {
        vector<vector<int>> ndp(d, vector<int>(2, 0));
        REP(k, d)
        ndp[(k + s[i] - '0') % d][0] = add(ndp[(k + s[i] - '0') % d][0], dp[k][0]);

        REP(l, s[i] - '0')
        REP(k, d)
        ndp[(k + l) % d][1] = add(ndp[(k + l) % d][1],dp[k][0]);
        REP(j, 10)
        REP(k, d)
        ndp[(k + j) % d][1] = add(dp[k][1], ndp[(k + j) % d][1]);
        dp = ndp;
    }

    int ans = 0;
    // cout << dp[0][1] << "\n";
    cout << sub(add(dp[0][1], dp[0][0]), 1);
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    long int n,a[11],i,j,sum=0;
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>a[i];
    }
    sort(a,a+n);
    for(i=0;i<n-1;i++)
    {
        sum+=a[i];
    }
    sum+=(a[n-1]/2);
    cout<<sum<<endl;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define ALL(vec) vec.begin(), vec.end()
#define rALL(vec) vec.rbegin(), vec.rend()
using namespace std;
using ll = long long;
// ------------------------------

int main() {
    int N;
    cin >> N;
    vector<int> a(N);
    rep(i, N) cin >> a[i];
    int ans = 0;
    rep(i, N) {
        if (i % 2 == 0 && a[i] % 2 == 1) ans += 1;
    }
    cout << ans << endl;
    return 0;
}

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

#define N 100005

int n, a[N];

int b[N], cnt[N];
bool vis[N];

int start;

double TL = 2.35;

using pii = pair <int, int>;

set <pii> st;

void dfs(int sz, int mn) {
	if (sz == n+1) {
        for (int i = 1; i < sz; i ++) printf("%d ", b[i]);
        exit(0);
	}
    if (1.0 * (clock() - start) / CLOCKS_PER_SEC > TL) {
        puts("-1");
        exit(0);
    }
    pii cur = *st.rbegin();
    if (cur.first == n - sz) {
        if (sz == 1 || sz > 1 && a[b[sz-1]] != cur.second) {
            int i = cur.second;
			b[sz] = i;
			st.erase(pii(cnt[i], i));
			if (!vis[a[i]]) {
				st.erase(pii(cnt[a[i]], a[i]));
				cnt[a[i]] --;
				st.insert(pii(cnt[a[i]], a[i]));
			}
			vis[i] = 1;
			dfs(sz+1, mn);
			vis[i] = 0;
			if (!vis[a[i]]) {
				st.erase(pii(cnt[a[i]], a[i]));
				cnt[a[i]] ++;
				st.insert(pii(cnt[a[i]], a[i]));
			}
			st.insert(pii(cnt[i], i));
        }
        else return;
    }
    else {
        while (vis[mn]) mn ++;
        for (int i = mn; i <= n; i ++) if (!vis[i]) {
            if (sz == 1 || sz > 1 && a[b[sz-1]] != i) {
                b[sz] = i;
                st.erase(pii(cnt[i], i));
                if (!vis[a[i]]) {
                    st.erase(pii(cnt[a[i]], a[i]));
                    cnt[a[i]] --;
                    st.insert(pii(cnt[a[i]], a[i]));
                }
                vis[i] = 1;
				dfs(sz+1, mn);
				vis[i] = 0;
                if (!vis[a[i]]) {
                    st.erase(pii(cnt[a[i]], a[i]));
                    cnt[a[i]] ++;
                    st.insert(pii(cnt[a[i]], a[i]));
                }
				st.insert(pii(cnt[i], i));
            }
        }
    }
    return;
}

int main() {
	start = clock();
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++) scanf("%d", &a[i]);
    bool flag = 0;
    int p = -1;
    for (int i = 1; i <= n; i ++) cnt[a[i]] ++;
	for (int i = 1; i <= n; i ++) st.insert(pii(cnt[i], i));
	dfs(1, 1);
    puts("-1");
	return 0;
}


Measured memory_bytes: 14592
x = int(input())
z = list(map(int,input().split()))
i = 1
num = 0
while i+1 < x:
    if z[i-1] < z[i] < z[i+1]:
        num += 1
    elif z[i+1] < z[i] < z[i-1]:
        num += 1
    i += 1
print(num)

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

#define pb push_back
#define For(i, j, k) for (int i = j; i <= k; i++)

using namespace std;

const int N = 1e5 + 10;

typedef long long LL;

vector<int> G[N];
int fa[N], rk[N], n, m;
int A[N], B[N];
LL dp[N], sum[N];

int find(int x) {
	return x == fa[x] ? x : fa[x] = find(fa[x]);
}

bool cmp(int x, int y) {
	return A[x] - B[x] < A[y] - B[y]; 
}

int main() {

	scanf("%d%d", &n, &m);
	For(i, 1, n) rk[i] = i, scanf("%d%d", &A[i], &B[i]);
	For(i, 1, m) {
		int u, v;
		scanf("%d%d", &u, &v);
		G[u].pb(v), G[v].pb(u);
	}
	
	sort(rk + 1, rk + n + 1, cmp);
	For(i, 1, n) {
		int o = rk[i];
		fa[o] = o;
		dp[o] = max(0, A[o] - B[o]), sum[o] = B[o];
		for (int v : G[o]) {
			if (!fa[v] || find(v) == o) continue;
			int x = find(v);
			fa[x] = o;
			dp[o] = min(dp[o], max(dp[x], A[o] - B[o] - sum[x]));
			sum[o] += sum[x];
		}
	}
	printf("%lld\n", dp[find(1)] + sum[find(1)]);

	return 0;
}

Measured memory_bytes: 9084
// 2020-07-04 16:59:27
#include<bits/stdc++.h>
#ifdef LOCAL
#include "lib/debug.hpp"
#else
#define debug(...) 1
#endif
#define ALL(a) (a).begin(), (a).end()
#define rep(i, n) REP(i, 0, (n))
#define repc(i, n) REPC(i, 0, (n))
#define REP(i, n, m) for (int i = (int)(n); i < (int)(m); i++)
#define REPC(i, n, m) for (int i = (int)(n); i <= (int)(m); i++)
#define REPCM(i, n, m) for (int i = (int)(n); i >= (int)(m); i--)
using namespace std;
using ll = long long;
using ld = long double;
using pr = pair<ll, ll>;
using vll = vector<ll>;
using vpr = vector<pr>;
template<class T> inline bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } else return false; }
template<class T> inline bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }

void answer() {
  auto isYY = [](string s) {
    return "00" <= s && s <= "99";
  };
  auto isMM = [](string s) {
    return "01" <= s && s <= "12";
  };
  auto isYYMM = [&](string s) {
    return isYY(s.substr(0, 2)) && isMM(s.substr(2, 2));
  };
  auto isMMYY = [&](string s) {
    return isMM(s.substr(0, 2)) && isYY(s.substr(2, 2));
  };
  string s;
  cin >> s;
  bool yymm = isYYMM(s);
  bool mmyy = isMMYY(s);
  string ans = "";
  if(yymm && mmyy) ans = "AMBIGUOUS";
  else if(!yymm && !mmyy) ans = "NA";
  else if(yymm && !mmyy) ans = "YYMM";
  else if(!yymm && mmyy) ans = "MMYY";
  cout << ans << '\n';
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  answer();
  return 0;
}

Measured memory_bytes: 3584
use strict;
use utf8;
use warnings;

my $n = <STDIN>;
chomp($n);
my $tarr = <STDIN>;
chomp($tarr);
my @tarr = split(" ", $tarr);
my $m = <STDIN>;
chomp($m);
my $sum = 0;
foreach my $i (@tarr){
  $sum += $i;
}

for (my $c = 0; $c < $m; $c++){
  my $ans = $sum;
  my $px = <STDIN>;
  chomp($px);
  my @px = split(" ", $px);
  my $x = pop(@px);
  my $a = pop(@px);
  $ans -= $tarr[$a-1] - $x;
  print "$ans\n";
}

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

using namespace std;

typedef long long ll;

#define INF 1e10
const int MOD = 1e9+7;

double dp[3333][3333];

int main(){
	int n;
	double p;
	cin >> n;
	cin >> p;
	dp[1][0]=1.0-p;
	dp[1][1]=p;
	for(int i = 2; i <= n; i++){
		cin >> p;
		for(int j = 1; j <= i; j++){
			dp[i][j]+=dp[i-1][j-1]*p;
		}
		for(int j = 0; j < i; j++){
			dp[i][j]+=dp[i-1][j]*(1.0-p);
		}
	}
	double ans = 0.0;
	for(int i = (n+1)/2; i <= n; i++)ans+=dp[n][i];
	cout << fixed << setprecision(10) << ans;
}


Measured memory_bytes: 78464
//
// Created by Hideaki Imamura on 2019-07-04.
//

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

ll gcd(ll x, ll y)
{
    ll r;
    while((r = x % y) != 0)
    {
        x = y;
        y = r;
    }
    return y;
}

int main() {
    ll n, x, xs[100010], tmp, d;
    cin >> n >> x;
    for(int i = 0; i < n; ++i) {
        cin >> tmp;
        xs[i] = x - tmp;
        if (xs[i] < 0) xs[i] = - xs[i];
    }

    d = xs[0];
    for(int i = 1; i < n; ++i) {
        d = gcd(d, xs[i]);
    }

    cout << d << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include<cstring>
#include<stdio.h>
using namespace std;
int  main() {
	int N = 0, W = 0, H = 0,count=0;
	cin >> H >> W >> N;
	if(H>W){
		if (N%H == 0)count = N / H; else count = N / H + 1;
	
	}else{
		if (N%W == 0)count = N / W; else count = N / W + 1;
	}
	cout<<count;

	return 0;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll  int
using namespace std;
int main() {
    ll n,d;
    cin>>n>>d;
    ll a[n][d];
    for(ll i=0;i<n;i++){
        for(ll j=0;j<d;j++)cin>>a[i][j];
    }
    ll ans=0;
    for(ll i=0;i<n;i++){
        for(ll j=i+1;j<n;j++){
            ll r=0;
            for(ll k=0;k<d;k++){
                r+=(a[i][k]-a[j][k])*(a[i][k]-a[j][k]);
            }
            long double r1=sqrt(r);
            
            if(r1-floor(sqrt(r))==0)ans++;
        }
    }
    cout<<ans<<"\n";
    
}



Measured memory_bytes: 3596
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define F first
#define S second
#define pb push_back
mt19937 rnd;


int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif

    int n;
    cin >> n;
    for (int i=n; i<=2*n; i++) {
        bool ok = 1;
        for (int j=2; j*j<=i; j++) {
            if (i%j == 0) {
                ok = 0;
                break;
            }
        }
        if (ok) {
            cout << i << "\n";
            break;
        }
    }

#ifdef LOCAL
    cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
   return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define pb push_back
#define ff first
#define ss second
#define rep(i,a,n) for(int i=a;i<n;i++)
#define M 1000000007
ll power(ll x, ll y, ll p)
{
    int res = 1;
    x = x % p;
    while (y > 0)
    {   if (y & 1)
        res = (res*x) % p;
        y = y>>1;
        x = (x*x) % p;
    }
    return res;
}
int main()
{
	IOS;
	ll n,m;
    cin>>n>>m;
  	ll ans=max((ll)0,(n*(n-1))/2)+max((ll)0,(m*(m-1))/2);
  cout<<ans;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define _GLIBCXX_DEBUG
static const int MAX = 20;


int main(){
  int n, p[MAX];
  cin >> n;
  rep(i, n) cin >> p[i];
  int count = 0;
  rep2(i, 1, n-1){
    if(p[i] > p[i+1] && p[i] < p[i-1]) count++;
    else if(p[i] < p[i+1] && p[i] > p[i-1]) count++;
  }
  cout << count << endl;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
#define endl '\n'
#define mod (int)(1e9+7)
#define fastIO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long int
using namespace std;
int gcd(int a, int b){
    return b == 0 ? a : gcd(b, a%b);
}
int lcm(int a, int b){
    return (a*b)/gcd(a,b);
}
int ncr(int n, int k){
    int res = 1;
    if ( k > n - k )
        k = n - k;

    for (int i = 0; i < k; ++i){
        res *= (n - i);
        res /= (i + 1);
    }
    return res;
}
int fibonacci(int n){
    double phi = (1 + sqrt(5))/(double)2;
    int nth_fib = round(pow(phi,n)/sqrt(5));
    return nth_fib;
}
int inv_mod(int a){
    int res = 1;
    int mod_temp = mod-2;
    while(mod_temp){
        if(mod_temp&1){
            res = ((res%mod)*(a%mod))%mod;
        }
        a = ((a%mod)*(a%mod))%mod;
        mod_temp >>= 1;
    }
    return res%mod;
}
signed main(){

#ifndef ONLINE_JUDGE
    //freopen("input.txt","r", stdin);
#endif
    fastIO

    int h, a;
    cin >> h >> a;
    int sum = 0;
    for(int i = 0,temp;i<a;i++){
        cin>> temp;
        h-=temp;
    }
    if(h<=0) cout << "Yes";
    else cout << "No";




    return 0;
}


Measured memory_bytes: 256
//Code by Anshuman Das Gupta

#include<bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define MOD 1000000007
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define loop(I,N) for(int i=I;i<N;i++)
#define sortvec(V) sort(V.begin(),V.end())
#define vec vector<int>
#define endl "\n"
using namespace std;
#define PI 3.14159265359
int fast_power(int base, int power) {
    int result = 1;
    while (power > 0) {

        if (power & 1) {
            result = (result * base) % MOD;
        }
        base = (base * base) % MOD;
        power = power >> 1;
    }
    return result % MOD;
}

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

int binsearch(int a[], int f, int r, int x) {
    while (f <= r) {
        int mid = (f + r) / 2;
        if (a[mid] == x)
            return mid;
        else if (a[mid] > x) {
            r = mid - 1;
        }
        else {
            f = mid + 1;
        }
    }
    return -1;
}
void sieve(int a[], int n) {
    a[0] = 0;
    a[1] = 0;
    for (int i = 2; i <= n; i++) {
        if (a[i] == 1) {
            for (int j = i + i; j <= n; j += i) {
                a[j] = 0;
            }
        }
    }
}

int32_t main() {
#ifndef ONLINE_JUDGE
    //for getting input from input.txt
    freopen("input.txt", "r", stdin);
    //for writing output to output.txt
    freopen("output.txt", "w", stdout);
#endif
    int t = 1;
    //cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int a[n];
        loop(0, n)
        cin >> a[i];
        sort(a, a + n);
        int ans = a[n - 1];
        int c = n - 2;
        int i = n - 2;
        int f = 0;
        while (c > 0) {
            f++;
            c--;
            ans += a[i];
            if (f == 2) {
                i--;
                f = 0;
            }
        }
        cout << ans << endl;
    }
    return 0;
}


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

#define filein freopen ("in.txt", "r", stdin)
#define fileout freopen ("out.txt", "w", stdout)
#define dbg(x) cerr << #x << ": " << x << endl

using namespace std;
typedef long long ll;

const int maxn = 105;
const ll inf = 10000000000;
ll w[maxn];
ll v[maxn];
ll dp[maxn][100005];
ll dp2[maxn][100005];

int main(){
	ll n,p;

	scanf("%lld %lld",&n,&p);
	ll sum = 0;
	for(ll i = 1; i <= n; i++){
		scanf("%lld %lld",w+i,v+i);
		sum += v[i];
	}

	for(ll i = 1; i <= 100000; i++)
		dp[0][i] = inf;

	for(ll i = 1; i <= n; i++){
		for(ll j = 1; j <= sum; j++){
			ll cost1 = inf;
			ll val1 = LLONG_MIN;
			ll cost2 = LLONG_MAX;
			ll val2 = LLONG_MIN;
			
			if(j >= v[i]){
				cost1 = dp[i-1][j-v[i]] + w[i];
				//val1 = dp2[i-1][j-v[i]] + v[i];
			}

			cost1 = min(cost1,dp[i-1][j]);
			//val2 = dp2[i-1][j];

			dp[i][j] = cost1;
			//printf("dp1[%lld][%lld]: %lld\n",i,j,dp[i][j]);
			//printf("dp2[%lld][%lld]: %lld\n\n",i,j,dp2[i][j]);
		}
	}
	ll ans = 0;
	for(ll i = 1; i <= sum; i++){
		//printf("dp[%lld][%lld]: %lld\n",n,i,dp2[n][i]);
		if(dp[n][i] <= p){
			ans = i;
		}
	}

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

Measured memory_bytes: 80128
#include <bits/stdc++.h>
#define rep(i, n) for (int i=0; i<(int)(n); i++)
#define all(v) v.begin(), v.end()
#define PRINT(v) for (auto x : (v)) cout <<x <<" " ; cout <<endl;
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using mat = vector<vector<ll>>;
const ll MOD = 1000000007;
const ll INF = 10000000000000000;
const int inf = 1001001001;
vector<int> x4 = {0, 1, 0, -1}, x8 = {0, 1, 1, 1, 0, -1, -1, -1};
vector<int> y4 = {1, 0, -1, 0}, y8 = {1, 1, 0, -1, -1, -1, 0, 1};
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; }
template<class T> inline T power(T a,T b,T m){ if (b==0) return 1;
  T tmp = power(a,b/2,m); if (b%2==0) return tmp*tmp%m; else return tmp*tmp%m*a%m; }
template<class T> inline T gcd(T a, T b){if (b==0) return a; return gcd(b, a%b);}
template<class T> inline T lcm(T a, T b){return a / gcd(a,b) * b;}
// ax+by=gcd(a,b)を解く
template<class T> inline T extgcd(T a,T b,T &x,T &y){if (b==0){x=1; y=0; return a;} T d=extgcd(b,a%b,y,x); y -= a/b*x; return d;}
void hey(){ cout <<"hey" <<endl; }

template<class T> struct edge { int to; T cost;};


int main() {
  int l,k; cin >>l >>k;
  vector<ll> dp(l+1, 0);
  // dp[i] := 高さiにする積み方は何通りあるか
  dp[1] = 1; // dark thin disk
  if (k <= l) dp[k] = 1; // dark white disk
  for (int i=1; i<l; i++){
    if (!dp[i]) continue;
    if (i+2 <= l) dp[i+2] += dp[i]; // + white thin disk + dark thin disk
    if (i+k+1<=l) dp[i+k+1] += dp[i]; // +white thin disk + dark thick disk
  }
  ll res = 0;
  for (int i=1; i<=l; i++) res += dp[i];
  cout <<res <<endl;
}


Measured memory_bytes: 3156
def shortests(n, x, y):
	short_lengths = {}
	for i in range(1, n + 1):
		for j in range(i + 1, n + 1):
			shortest = min(j - i, abs(i - x) + abs(j - y) + 1, abs(i - y) + abs(j - x) + 1)
			short_lengths[shortest] = short_lengths.get(shortest, 0) + 1
	for leng in range(1, n):
		if leng not in short_lengths:
			print(0)
		else:
			print(short_lengths[leng])

inputs = input().split(' ')
inputs = [int(x) for x in inputs]
n = inputs[0]
x = inputs[1]
y = inputs[2]

shortests(n, x, y)

Measured memory_bytes: 3572
#include<stdio.h>
#define MAXN 1000+5
#define INF -1
struct node
{
	int r,l,p;
}T[MAXN];
void began(int u)
{
	if(u==INF)return;
	printf(" %d",u);
	began(T[u].l);
	began(T[u].r);
}
void middle(int u)
{
	if(u==INF)return;
	middle(T[u].l);
	printf(" %d",u);
	middle(T[u].r);
}
void endl(int u)
{
	if(u==INF)return;
	endl(T[u].l);
	endl(T[u].r);
	printf(" %d",u);
}
int main()
{
	int N,root;
	scanf("%d",&N);
	int i,v,R,L;
	for(i=0;i<N;i++)
	{
		T[i].l=INF;
		T[i].p=INF;
		T[i].r=INF;	
	} 
	for(i=0;i<N;i++)
	{
		scanf("%d%d%d",&v,&L,&R);
		T[v].l=L;
		T[v].r=R;
		if(L!=INF)T[L].p=v;
		if(R!=INF)T[R].p=v; 
	}
	for(i=0;i<N;i++)if(T[i].p==INF)root=i;
	printf("Preorder\n");
	began(root);
	printf("\n");
	printf("Inorder\n");
	middle(root);
	printf("\n");
	printf("Postorder\n");
	endl(root);
	printf("\n");
	return 0;
	return 0;
} 


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

struct low_link {
public :
	vector<int> articulation;
	vector<pair<int, int>> bridge;
private :
	int n;
	vector<vector<int>> g;
	vector<int> order, low;
	vector<bool> seen;

	int dfs (int v, int p, int ord) {
		seen[v] = true;
		order[v] = ord++;
		low[v] = order[v];
		int child = 0;
		bool isart = false;
		for (int u : g[v]) if (u != p) {
			if (seen[u]) {
				low[v] = min(low[v], order[u]);
				continue;
			}
			child++;
			ord = dfs(u, v, ord);
			low[v] = min(low[v], low[u]);
			if (p != -1) isart |= (order[v] <= low[u]);
			if (order[v] < low[u]) bridge.push_back(minmax(v, u));
		}
		isart |= (p == -1 and child >= 2);
		if (isart) articulation.push_back(v);
		return ord;
	}

public :
	low_link (int n) : n(n), g(n), order(n), low(n), seen(n) { }

	void add_edge (int v, int u) {
		g[v].push_back(u);
		g[u].push_back(v);
	}

	void build (int r = 0) {
		bridge.clear();
		articulation.clear();
		fill(order.begin(), order.end(), 0);
		fill(low.begin(), low.end(), 0);
		fill(seen.begin(), seen.end(), false);
		dfs(r, -1, 0);
	}

};


int main() {
	int n, m;
	cin >> n >> m;
	low_link g(n);
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		g.add_edge(--a, --b);
	}
	
	g.build(0);
	
	cout << g.bridge.size() << '\n';
	
	return 0;
}

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

int main() {
  int N,K,d,A;
  cin >> N >> K;
  int has_treat[200]={};
  
  for (int i=0;i<K;i++) {
    cin >> d;
    for (int j=0;j<d;j++) {
      cin >> A;
      has_treat[A]=1;
    }
  }
  int notreat=0;
  for (int l=0;l<N;l++) {
    if (has_treat[l+1]==0) {
      notreat++;
    }
  }
  cout << notreat << endl;
}


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

using namespace std;

int main()
{
    int a,b,c,y,x,i,j,k;
    scanf("%d%d%d%d%d",&a,&b,&c,&x,&y);

    vector <int> v;
    int sum;

    // only a b
    sum = a*x+b*y;
    v.push_back(sum);

    // only c
    int n= max(x,y);
    sum = n*2*c;
    v.push_back(sum);

    // b direct, a share
    sum = x*2*c;
    i = y - x;
    if(i>0)
    {
        sum = sum + (i*b);
       //printf("i %d ",i);
    }
    v.push_back(sum);

    // A direct, b share
    sum = y*2*c;
    i = x - y;
    if(i>0)
        {
            sum = sum + (i*a);
             //printf("j %d ",i);
        }
        v.push_back(sum);

    sort(v.begin(),v.end());

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

   return 0;
}



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

int main()
{
    int n;
    cin>>n;
    string s;
    map<string,int> map;
    int mx=0;
    for(int i=0;i<n;i++)
    {
        cin>>s;
        map[s]++;
        if(map[s]> mx)
            mx=map[s];
    }
    for(auto x : map)
    if(mx==x.second)
        cout << x.first <<  endl;
    return 0;
}


Measured memory_bytes: 19232
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,a,b) for(int i=(a),_end_=(b);i<=_end_;i++)
#define DREP(i,a,b) for(int i=(a),_end_=(b);i>=_end_;i--)
#define EREP(i,a) for(int i=start[(a)];i;i=e[i].next)
template<class T>inline void chkmax(T &a,T b){ if(a<b)a=b;}
template<class T>inline void chkmin(T &a,T b){ if(a>b)a=b;}
#define fi first
#define se second
#define mkr(a,b) make_pair(a,b)
inline int read()
{
	int sum=0,p=1;char ch=getchar();
	while(!(('0'<=ch && ch<='9') || ch=='-'))ch=getchar();
	if(ch=='-')p=-1,ch=getchar();
	while('0'<=ch && ch<='9')sum=sum*10+ch-48,ch=getchar();
	return sum*p;
}

#define int ll

const int maxn=2e5+20;
const ll inf=1ll<<60;

int a[maxn],x[maxn],y[maxn],n,as[maxn];
int xs[maxn],ys[maxn];
int L[maxn],R[maxn];

inline void init()
{
	n=read();
	REP(i,1,n)a[i]=read(),x[i]=~a[i]&1,y[i]=a[i]<=2?2-a[i]:(a[i]&1);
	REP(i,1,n)xs[i]=xs[i-1]+x[i],ys[i]=ys[i-1]+y[i],as[i]=as[i-1]+a[i];
	L[0]=0;
	int mn=0;
	REP(i,1,n)
	{
		chkmin(mn,as[i]-ys[i]);
		L[i]=mn+ys[i];
	}
	R[n]=0;
	mn=as[n]-as[n] + ys[n];
	DREP(i,n-1,0)
	{
		chkmin(mn,as[n]-as[i]+ys[i]);
		R[i]=mn-ys[i];
	}
	int ans=inf;
	mn=inf;
	REP(i,0,n)
	{
		chkmin(mn,L[i]-xs[i]);
		chkmin(ans,mn+R[i]+xs[i]);
	}
	printf("%lld\n",ans);
}

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



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

//#define int long long
#define ll long long
#define all(v) (v).begin(), (v).end()
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<n;++i)
#define gearup ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef pair<ll, ll> P;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<vector<vector<ll>>> vvvl;
ll MOD = 1000000007;
const long long INF = 1LL << 60;
//cout<<fixed<<setprecision(10);

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> void debug(T v){rep(i,v.size()) cout<<v[i]<<" ";cout<<endl;}

signed main()
{   
    gearup;
    ll n;string s, t;
    cin >> n >> s >> t;
    rep(i,n)cout <<s[i]<<t[i];
    cout << endl;
}


Measured memory_bytes: 256