akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

int n, a, b, c, d;
string s;

bool check(int start, int goal)
{
    int count = 0;
    for (int i = start; i < goal; ++i)
    {
        if (s[i] == '#')
        {
            ++count;
        }
        else
        {
            count = 0;
        }

        if (count >= 2)
        {
            return false;
        }
    }
    return true;
}

bool exist_air(int start, int goal)
{
    int count = 0;
    for (int i = start; i < goal; ++i)
    {
        if (s[i] == '.')
        {
            ++count;
        }
        else
        {
            count = 0;
        }

        if (count >= 3)
        {
            return true;
        }
    }
    return false;
}

int main()
{
    cin >> n >> a >> b >> c >> d;
    cin >> s;

    --a, --b, --c, --d;
    bool flag = check(a + 1, c) && check(b + 1, d);
    if (c < d)
    {
        if (flag)
        {
            cout << "Yes" << endl;
        }
        else
        {
            cout << "No" << endl;
        }
    }
    else
    {
        if (flag && exist_air(b - 1, d + 2))
        {
            cout << "Yes" << endl;
        }
        else
        {
            cout << "No" << endl;
        }
    }
}

Measured memory_bytes: 640
import heapq

n, m = map(int, input().split())
a = [-int(x) for x in input().split()]

heapq.heapify(a)
for _ in range(m):
   mina = heapq.heappop(a)
   heapq.heappush(a, (-mina//2)*(-1))

print(-sum(a))


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

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int [] values = new int [3];
		for (int i = 0; i < 3; i++) {
			values[i] = sc.nextInt();
		}
		Arrays.sort(values);
		int val = values[0] + values[1];
		System.out.println(val);
	}

}


Measured memory_bytes: 35816
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<queue>
#include<stack>
#define int long long
using namespace std;
int n, m;
int a[50], b[50], c[50], d[50][50];
signed main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++)for (int j = 1; j <= m; j++)cin >> d[i][j];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			int p; cin >> p;
			if ((i + j) % 3 == 1)b[p]++;
			else if ((i + j) % 3 == 2)c[p]++;
			else a[p]++;
		}
	}
	int ans = 500*500*1000;
	for (int i = 1; i <= m; i++)for (int j = 1; j <= m; j++) {
		if (i == j)continue;
		for (int k = 1; k <= m; k++) {
			if (j == k || k == i)continue;
			int cnt = 0, p;
			for (p = 1; p <= m; p++)cnt += a[p] * d[p][i];
			for (p = 1; p <= m; p++)cnt += b[p] * d[p][j];
			for (p = 1; p <= m; p++)cnt += c[p] * d[p][k];
			ans = min(ans, cnt);
		}
	}cout << ans << endl;
}

Measured memory_bytes: 256
using namespace std;

#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <limits>
#include <climits>
#include <vector>
#include <string>
#include <set>
#include <queue>
#include <stack>
#include <map>
typedef long long ll;
typedef pair<int,int> p;

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




int main()
{
  // input & declare
  int n;
  cin >> n;
  std::vector<int> v;
  int tmp;
  for(int i = 0; i < n; i++)
  {
    cin >> tmp;
    v.push_back(tmp);
  }
  sort(v.begin(),v.end());


  // process
  ll result = 0;
  for(int i = 1; i < n; i += 2){
    // std::cout << i << '\n';
    if (n % 2 == 0) {
      if (v[i-1] == v[i] && v[i] == i) {
        result++;
      }else{
        std::cout << "0" << '\n';
        exit(0);
      }
    }
    else if(n % 2 == 1){
      if (i == 1){
        v.erase(v.begin());
      }
      if (v[i-1] == v[i] && v[i] == i+1) {
        result++;
      }else{
        std::cout << "0" << '\n';
        exit(0);
      }
    }
  }

  int ans = 1;
  for(int i = 0; i < result; i++){
    ans *= 2;
    if (ans > 1000000007) {
      ans %= 1000000007;
    }
  }

  // output
  std::cout << ans << '\n';
}


Measured memory_bytes: 892
# -*- coding: utf-8 -*-
N, T = map(int, raw_input().split())

ret_cost = 1001
ret_time = 1001

for i in range(N):
	c,t = map(int, raw_input().split())
	if t <= T and c <= ret_cost:
		ret_time = t
		ret_cost = c

if ret_time > T:
	print('TLE')
else :
	print(ret_cost)


Measured memory_bytes: 2568
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
#include <cmath>
#include <bitset>
#include <complex>
#include <functional>
#include <numeric>
#include <iomanip>

// output
#define SPBR(w, n) std::cout<<(w + 1 == n ? '\n' : ' ');
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
// utility
#define ALL(i) (i).begin(), (i).end()
#define FOR(i, a, n) for(int i=(a);i<(n);++i)
#define RFOR(i, a, n) for(int i=(n)-1;i>=(a);--i)
#define REP(i, n) for(int i=0;i<int(n);++i)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define IN(a, x, b) (a<=x && x<b)
#define OUT(a, x, b) (x<a || b<=x)
template<class T> inline T chmax(T & a, const T b) { return a = (a < b) ? b : a; }
template<class T> inline T chmin(T& a, const T b) { return a = (a > b) ? b : a; }

// type/const
#define int ll
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const int MOD = 1000000007;
/* const int MOD = 998244353; */
const int INF = 1e18;
const double PI = acos(-1);

using namespace std;
struct INIT { INIT(){
  cin.tie(0); ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
}}INIT;


signed main() {
  int N; 
  cin >> N;

  int ans = 0;
  for(int i = 1; i*i <= N; i++){
    if((N-i)%i == 0){
      int x = (N-i)/i;
      if(x > i) ans += x;
    }
  }

  cout << ans << "\n";

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define ll long long
#define ll_MAX LONG_LONG_MAX
#define ll_MIN LONG_LONG_MIN
#define pi pair<int, int>
#define endl "\n"
#define MAXN 100005
using namespace std;

int n, x, t;

void solve()
{
    cin >> n >> x >> t;
    int ans;
    (n % x == 0) ? ans = (n / x) *t : ans = (n / x + 1) * t;
    cout << ans << endl;
}

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

Measured memory_bytes: 3644
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
    int n, pmax, count = 1;
    cin >> n;
    vector<int> p(n);
    for(int i = 0; i < n; i++){
        scanf("%d", &p[i]);
    }
    pmax = p[0];
    for(int i = 1; i < n; i++) {
        if(p[i] <= pmax) count++;
        pmax = min(pmax, p[i]);
    }
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <vector>
#define MOD 1000000007
#define INT long long int
#define REP(i,n) for(int(i)=0;(i)<(n);(i)++) 
using namespace std;
const long long INF = numeric_limits<long long>::max();


int main()
{
  int K,T;
  cin>>K>>T;
  int a[T];
  int amax=0;
  int sum=0;
  REP(i,T){
    cin>>a[i];
    amax = max(amax,a[i]);
    sum += a[i];
  }
  sum-=amax;
  int ans = max(0,amax-sum-1);
  cout<<ans<<endl;
  return 0;
}

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

using ll = long long;

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

  if (A>=13) {
    cout << B << endl;
    return 0;
  } else if (A <= 12 && 6<= A) {
    cout << B/2 << endl;
    return 0;
  } else {
    cout << 0 << endl;
  }

}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(){
  int N, tmp;
  cin >> N;
  int count = 0;
  for (int i=1; i<=N; i++){
    cin >> tmp;
    if (i != tmp){
      count++;
    }
	if (count > 2){
      break;
    }
  }
  cout << (count <= 2 ? "YES" : "NO") << endl;
  return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

import static java.lang.Integer.parseInt;

/**
 * Paint Color
 */
public class Main {

	static final int[][] HV = {
			{1, 0},
			{-1, 0},
			{0, 1},
			{0, -1},
	};

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

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line;
		String[] words;

//		long ts = System.nanoTime();

		while ((line = br.readLine()) != null && !line.isEmpty()) {

			int w, h, n;
			w = parseInt(line.substring(0, line.indexOf(' ')));
			h = parseInt(line.substring(line.indexOf(' ') + 1));
			if ((w | h) == 0) break;

			n = parseInt(br.readLine());

			int[][] masks = new int[n][4];
			Map<Integer, Integer> xs = new TreeMap<>();
			Map<Integer, Integer> ys = new TreeMap<>();
			xs.put(-1, 0);
			ys.put(-1, 0);
			xs.put(w, 0);
			ys.put(h, 0);

			for (int i = 0; i < n; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				//
				int x1, y1, x2, y2;
				x1 = parseInt(st.nextToken());
				y1 = parseInt(st.nextToken());
				x2 = parseInt(st.nextToken());
				y2 = parseInt(st.nextToken());
				//
				masks[i][0] = x1;
				masks[i][1] = y1;
				masks[i][2] = x2;
				masks[i][3] = y2;
				//
				xs.put(x1, 0);
				xs.put(x2, 0);
				ys.put(y1, 0);
				ys.put(y2, 0);
				xs.put(x1 - 1, 0);
				ys.put(y1 - 1, 0);
			}

			//compress
			int _i = 0;
			for (int k : xs.keySet()) {
				xs.put(k, _i);
				_i++;
			}
			_i = 0;
			for (int k : ys.keySet()) {
				ys.put(k, _i);
				_i++;
			}

			//mask
			boolean[][] board = new boolean[xs.size()][ys.size()];
			for (int i = 0; i < board.length; i++) {
				for (int j = 0; j < board[0].length; j++) {
					if (i == 0 || i == board.length - 1
							|| j == 0 || j == board[0].length - 1)
						board[i][j] = true;
				}
			}

			for (int i = 0; i < n; i++) {
				int x1, y1, x2, y2;
				x1 = masks[i][0];
				y1 = masks[i][1];
				x2 = masks[i][2];
				y2 = masks[i][3];
				for (int j = xs.get(x1); j < xs.get(x2); j++) {
					for (int k = ys.get(y1); k < ys.get(y2); k++) {
						board[j][k] = true;
					}
				}
			}

//			for (int i = 0; i < board.length; i++) {
//				for (int j = 0; j < board[0].length; j++) {
//					System.out.print(board[i][j] ? '*' : ' ');
//				}
//				System.out.println();
//			}
//			System.out.println();

			//paint
			int colors = 0;
			for (int i = 1; i < board.length - 1; i++) {
				for (int j = 1; j < board[0].length - 1; j++) {
					if (!board[i][j]) {
						Deque<int[]> q = new ArrayDeque<>();
						q.offer(new int[]{i, j});
						board[i][j] = true;
						colors++;
						while (!q.isEmpty()) {
							int[] p = q.poll();
							int x, y;
							x = p[0];
							y = p[1];
							for (int k = 0; k < HV.length; k++) {
								int nx, ny;
								nx = x + HV[k][0];
								ny = y + HV[k][1];
								if (!board[nx][ny]) {
									board[nx][ny] = true;
									q.offer(new int[]{nx, ny});
								}
							}
						}
					}
				}
			}
			System.out.println(colors);

//		System.out.println((System.nanoTime() - ts) / 1000 / 1000);
		}//end while
	}//end main
}

Measured memory_bytes: 70720
h,w,x,y = map(int,input().split())
print(h*w/2,end=" ")
if h%2 != 0 or w%2 != 0:
  print(0)
else:
  if int(h/2) == x and int(w/2) == y:
    print(1)
  else:
    print(0)

Measured memory_bytes: 2940
# AOJ 0099 Surf Smelt Fishing Contest II
# Python3 2018.6.22 bal4u

import heapq
MAX = 1000000
SFT = 20	# 2**20 = 1048576 > MAX
Q = []

# tbl[0:キー, 1:Magic]
tbl = [[0 for j in range(2)] for i in range(MAX+2)]
n, q = list(map(int, input().split()))
for i in range(q):
	id, v = list(map(int, input().split()))
	tbl[id][0] += v
	tbl[id][1] += 1
	heapq.heappush(Q, ((-tbl[id][0] << SFT)|id, id, tbl[id][1]))
	while 1:
		f, id, c = Q[0]       # 要素の確認のみ
		if tbl[id][1] == c:
			print(id, tbl[id][0])
			break
		heapq.heappop(Q)


Measured memory_bytes: 122992
#include <iostream>
#include <string>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <numeric>
#define MOD 1000000007

typedef long long ll;
using namespace std;

int main(void) {
    ll n;
    cin >> n;
    ll i,j;
    int m;
    ll sum=0;
    for(i=1;i<10000000;i++){
        if((n-i)%i == 0 && i<(n-i)/i){
            sum += (n-i)/i;
        }
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

long long solve(long long N){
    long long res = 0;
    for(int a=1;;a++){
        auto r = N-a;
        auto m = r/a;
        if(m < a) break;
        if(r%a == 0 && a < m) res += m;
    }
    return res;
}

int main(){
    long long N;
    while(cin >> N){
        cout << solve(N) << endl;
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#include <string>
#include <set>
#include <bitset>
#include <unordered_map>

using namespace std;
using ll = long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;
template <class T>
using Vvec = vector<vector<T> >;

int main()
{
    int N;
    cin >> N;
    for(int i=1; i<10; i++){
        for(int j=1; j<10; j++){
            if(i*j==N){
                cout << "Yes\n"; return 0;
            }
        }
    }
    cout << "No\n";
}

Measured memory_bytes: 256
//============================================================================
// Name        : Hello5.cpp
// Author      :
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

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

int main() {
string s;
cin>>s;
int ans=0;
int m=s.size();
rep(i,m/2)
if (
s[i]==s[m-i-1])
ans+=1;
rep(l,m/4)
if(s[l]==s[m/2-l-1])
{
	ans+=1;
}



if (ans==m/2+m/4){
	cout<<"Yes"<<endl;
}

else cout<<"No"<<endl;

	  return 0;
	}





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

const int maxN = 1e5 + 10;
int a[maxN] = {0};

int main(){
    int n, sum = 0;
    cin >> n;
    for(int i = 0; i  < n; i++){
        cin >> a[i];
        sum = sum + a[i];
    }
    int m, p, x;
    cin >> m;
    for(int i = 0 ; i < m ; i ++){
        cin >> p >> x;
        cout << sum - a[p - 1] + x << '\n';
    }

}

Measured memory_bytes: 256
import sys
bingo = [[],[],[]]
 
for i in range(3):
  a, b, c = map(int,input().split())
  bingo[i].append(a)
  bingo[i].append(b)
  bingo[i].append(c)
  
N = int(input())
  
for i in range(N):
  S = int(input())
  for j in range(3):
    if S in bingo[j]:
      for k in range(3):
        if S == bingo[j][k]:
          bingo[j][k] = 'ok'
          
ANS = 0
 
for i in range(3):
  for j in range(3):
    if bingo[i][j] == 'ok':
      ANS += 1
      if ANS == 3:
        print("Yes")
        sys.exit()
  ANS = 0
 
for i in range(3):
  for j in range(3):
    if bingo[j][i] == 'ok':
      ANS += 1
      if ANS == 3:
        print("Yes")
        sys.exit()
  ANS = 0
 
if bingo[1][1] == 'ok':
  if bingo[0][0] == 'ok' and bingo[2][2] == 'ok':
    print("Yes")
    sys.exit()
  elif bingo[0][2] == 'ok' and bingo[2][0] == 'ok':
    print("Yes")
    sys.exit()
  else:
    print("No")
    sys.exit()
print("No")

Measured memory_bytes: 3064
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;
inline ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
inline ll lcm(ll a, ll b) { return a / gcd(a, b)*b; }
template<class S,class T> ostream& operator << (ostream& out,const pair<S,T>& o){ out << "(" << o.first << "," << o.second << ")"; return out; }
template<class T> ostream& operator << (ostream& out,const vector<T> V){ for(int i = 0; i < V.size(); i++){ out << V[i]; if(i!=V.size()-1) out << " ";} return out; }
template<class T> ostream& operator << (ostream& out,const vector<vector<T> > Mat){ for(int i = 0; i < Mat.size(); i++) { if(i != 0) out << endl; out << Mat[i];} return out; }
template<class S,class T> ostream& operator << (ostream& out,const map<S,T> mp){ out << "{ "; for(auto it = mp.begin(); it != mp.end(); it++){ out << it->first << ":" << it->second; if(mp.size()-1 != distance(mp.begin(),it)) out << ", "; } out << " }"; return out; }

/*
 <url:https://atcoder.jp/contests/dp/tasks/dp_c>
 問題文============================================================
 =================================================================
 解説=============================================================
 dp[i][j] := i日目で、前日の生活がjの場合の最大値
 ================================================================
 */


template<class Type>
Type solve(Type res = Type()){
    int N; cin >> N;
    vector<vector<ll>> abc(N,vector<ll>(3));
    for(int i = 0; i < N;i++) for(int j = 0; j < 3;j++) cin >> abc[i][j];
    
    vector<vector<ll>> dp(2,vector<ll>(3,0));
    int cur = 0,next = 1;
    for(int i = 0; i < N;i++){
        for(int j = 0; j < 3;j++){
            for(int k = 0; k < 3;k++){
                if(j==k) continue;
                dp[next][k] = max(dp[next][k],dp[cur][j]+abc[i][k]);
            }
            dp[cur][j] = 0;
        }
        swap(cur,next);
    }
    res = *max_element(dp[cur].begin(), dp[cur].end());
    return res;
}
int main(void) {
    cin.tie(0); ios_base::sync_with_stdio(false);
    // solve(0);
    cout << fixed << setprecision(15) << solve<ll>() << endl;
    return 0;
}


Measured memory_bytes: 5760
N = int(input())
A = list(map(int,input().split()))
step = []
before = A[0]
for i in range(1, N):
   if A[i] - before >= 0:
      step.append(0)
      before = A[i]
   else:
      step.append(-A[i] + before)
ans = sum(step)   
print(ans)

Measured memory_bytes: 106932
#include<stdio.h> 
int main(){ 
    int a, b,c,cnt=0; 
    scanf("%d %d %d",&a, &b, &c); 
    for (int i = a; i <= b; ++i) { 
        if (c%i == 0) ++cnt; 
        } 
        printf("%d\n", cnt); 
        return 0; 
    
} 


Measured memory_bytes: 2712
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.PrintStream;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Ribhav
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastReader in = new FastReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        BYYMMOrMMYY solver = new BYYMMOrMMYY();
        solver.solve(1, in, out);
        out.close();
    }

    static class BYYMMOrMMYY {
        public void solve(int testNumber, FastReader s, PrintWriter out) {
            int S = s.nextInt();
            boolean l = 1 <= S / 100 && S / 100 <= 12, r = 1 <= S % 100 && S % 100 <= 12;
            if (l && r) System.out.println("AMBIGUOUS");
            else if (l && !r) System.out.println("MMYY");
            else if (!l && r) System.out.println("YYMM");
            else System.out.println("NA");
        }

    }

    static class FastReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private FastReader.SpaceCharFilter filter;

        public FastReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public int nextInt() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public boolean isSpaceChar(int c) {
            if (filter != null) {
                return filter.isSpaceChar(c);
            }
            return isWhitespace(c);
        }

        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }
}



Measured memory_bytes: 21460
#include <bits/stdc++.h>
using namespace std;
bool ans[5005];
int a[5005], n, k;
bool check(int x) {
  bool skipped = false;
  bitset<5000> bs;
  bs[0] = 1;
  for (int i = 0; i < n; i++) {
    if (a[i] == x && !skipped) {
      skipped = true;
      continue;
    }
    if (a[i] < k) {
      bs |= (bs << a[i]);
    }
  }
  bool ret = false;
  for (int i = k - 1; i >= max(0, k - x); i--) {
    ret |= bs[i];
  }
  return ret;
}
int main() {
  scanf("%d %d", &n, &k);
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
  }
  sort(a, a + n);
  a[n] = 9999;
  int lo = 0, hi = n;
  while (lo < hi) {
    int mid = (lo + hi) / 2;
    if (a[mid] >= k || check(a[mid])) {
      hi = mid;
    } else {
      lo = mid + 1;
    }
  }
  int cnt = 0;
  for (int i = 0; i < n; i++) {
    if (a[i] < k) {
      cnt += a[i] >= a[lo];
    } else {
      cnt++;
    }
  }
  printf("%d\n", n - cnt);
  return 0;
}

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

using namespace std;

int main(){
	ios_base::sync_with_stdio(0);
  	cin.tie(NULL);
  	long long n;
  	cin >> n;
  	long long b = 1;
  	while(2 * b <= n) b *=2;
   	cout << 2 * b - 1 << endl;
	return 0;
}

Measured memory_bytes: 256
#include<cstdio>
using namespace std;
int n,sum[2005][2005],u[2005][2005],m,l[2005][2005],t[2005][2005];
char map[2005][2005];
int main()
{
	int q,x1,y1,x2,y2;
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=n;i++) scanf("%s",map[i]+1);
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++){
		sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
		u[i][j]=u[i-1][j]+u[i][j-1]-u[i-1][j-1];
		l[i][j]=l[i-1][j];t[i][j]=t[i][j-1];
		if(map[i][j]=='1'){
			sum[i][j]++;
			if(map[i-1][j]=='1') u[i][j]++,t[i][j]++;
			if(map[i][j-1]=='1') u[i][j]++,l[i][j]++;
		}
	}
	while(q--)
	{
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		printf("%d\n",sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1]-(u[x2][y2]-u[x1-1][y2]-u[x2][y1-1]+u[x1-1][y1-1]-t[x1][y2]-l[x2][y1]+t[x1][y1-1]+l[x1-1][y1]));
	}
	return 0;
}

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

int main() {
    string s, t;
    cin >> s >> t;
    // s = "contest";
    // t = "son";
    int n = sz(s), m = sz(t);
    vector< vector< int > > is(26);
    rep(i, n) is[s[i] - 'a'].push_back(i);
    rep(i, n) is[s[i] - 'a'].push_back(i+n);

    // for (int i = 0; i < s.size(); i++) {
    //     cout << "--" << s[i] - 'a' << "--" << endl;
    // }

    // for (int i = 0; i < is.size(); i++) {
    //     cout << "--" << i << "--" << endl;
    //     for (int j = 0; j < is[i].size(); j++) {
    //         cout << is[i][j] <<endl;
    //     }
    // }
    ll ans = 0;
    int p = 0;

    // t の探索
    rep(i, m) {
        int c = t[i] - 'a';
        if (sz(is[c]) == 0) {
            puts("-1");
            return 0;
        }
        p = *lower_bound(is[c].begin(), is[c].end(), p)+1;
        // cout << p << endl;
        // cout << ans << endl;

        if (p >= n) {
            // cout << "ddd" << endl;
            p -= n;
            ans += n;
        }
    }
    ans += p;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1724
from collections import Counter
import sys


class UnionFind:
    def __init__(self, n):
        self.table = [-1] * n

    def _root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x

    def find(self, x, y):
        return self._root(x) == self._root(y)

    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1


def main():
    n, k, l = map(int, sys.stdin.buffer.readline().split())
    a = UnionFind(n)
    b = UnionFind(n)
    cnt = 0
    for x in sys.stdin.buffer.readlines():
        p, q = map(int, x.split())
        cnt += 1
        if cnt <= k:
            a.union(p-1, q-1)
        else:
            b.union(p-1, q-1)

    pairs = []
    for i in range(n):
        pairs.append((a._root(i), b._root(i)))

    d = Counter(pairs)
    ans = [d[x] for x in pairs]
    print(*ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 49424
#include<bits/stdc++.h>
#define int long long
#define all(x) x.begin(),x.end()
#define input freopen("/Users/shahadat/Desktop/input.txt", "r", stdin)

int const MOD = 1e9 + 7;
using namespace std;


int dp[200010], num[200010];
int32_t main(){
    int n, k;
    cin>>n>>k;
    for(int i = 1; i<=n; i++)
        cin>>num[i];
    
    for(int i = 2; i<=n; i++)
        dp[i] = 1e9+7;

    dp[1] = 0;
    for(int i = 1; i<=n; i++){
        for(int j = 1; j<=k; j++){
            dp[i+j] = min(dp[i+j], dp[i] + abs(num[i] - num[i+j]));
        }
    }
    cout<<dp[n]<<endl;
}


Measured memory_bytes: 1792
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#include <bitset>     //UWAGA - w czasie kompilacji musi byc znany rozmiar wektora - nie mozna go zmienic
#include <cassert>
#include <iomanip>        //do setprecision
#include <ctime>
#include <complex>
using namespace std;

#define FOR(i,b,e) for(int i=(b);i<(e);++i)
#define FORQ(i,b,e) for(int i=(b);i<=(e);++i)
#define FORD(i,b,e) for(int i=(b)-1;i>=(e);--i)
#define REP(x, n) for(int x = 0; x < (n); ++x)

#define ST first
#define ND second
#define PB push_back
#define MP make_pair
#define LL long long
#define ULL unsigned LL
#define LD long double

const double pi = 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342;
const int mod=1000000007;

//テストしてない！

//iの親:i/2
//iの子:2*i+0,2*i+1
//iの兄弟:i^1
//iの深さ//log_2 iの整数部分


struct segtree {//segtree seg=segtree(n);//n:データ数  0-index 基本半区間？
  LL seg_unit=0;//単位元 minなら2e9など
  LL segfunc(LL a,LL b){
    return max(a,b);
  }
    int N=1;
    vector<LL> dat, sum;
    segtree(int n) {//n:データ数
        N = 1;
        while(N < n) N <<= 1;
        dat.assign(2*N-1,seg_unit);
        sum.assign(2*N-1,0);
    }
    void set_dat(int k, LL a){
      k += N-1; // leaf
      dat[k] = a;
    }
    void set_func(){
      for(int i=N-1; i>0; --i) dat[i] = segfunc(dat[i*2+0], dat[i*2+1]);
    }
    void update(int k, LL a) {//dat[k]=a
        k += N-1; // leaf
        dat[k] = a;
        while(k > 0) {
            k = (k - 1) / 2;
            dat[k] = segfunc(dat[k*2+1], dat[k*2+2]);
        }
    }
    void add(int a, int b, int x) { add(a,b,x,0,0,N); }
    int add(int a, int b, int x, int k, int l, int r) {//区間和
        if(b <= l || r <= a) return dat[k];
        if(a <= l && r <= b) {
            sum[k] += x;
            return dat[k] += x;
        }
        int m = (l+r)/2;
        return dat[k] = segfunc(add(a,b,x,2*k+1,l,m),add(a,b,x,2*k+2,m,r))+sum[k];
    }
    LL query(int a, int b) { return query(a,b,0,0,N); }
    LL query(int a, int b, int k, int l, int r) {
        if(b <= l || r <= a) return seg_unit;
        if(a <= l && r <= b) return dat[k];
        int m = (l+r)/2;
        return segfunc(query(a,b,2*k+1,l,m),query(a,b,2*k+2,m,r))+sum[k];
    }
};



int main(){
	int n;
	cin>>n;
	vector<LL> h(n);
	vector<LL> a(n);
	FOR(i,0,n)cin>>h[i];
	FOR(i,0,n)cin>>a[i];
	segtree t(n+1);
	LL ans=0;
	FOR(i,0,n){
		LL tmp=t.query(0,h[i]);
		t.update(h[i],tmp+a[i]);
		ans=max(ans,tmp+a[i]);
	}
	cout<<ans<<endl;
    return 0;
}


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

using namespace std;

int cs(int k){
  int l = 0;
  while(k>0){
    l+=k%10;
    k/=10;
  }
  return l;
}

int main(){
  int n,a,b;
  cin >> n >> a >> b;
  int ans =0;
  for(int i = 1;i<=n;i++)
    ans+=i*(cs(i)>=a&&cs(i)<=b);
  cout << ans;
  return 0;
}


Measured memory_bytes: 256
a, b = map(int, input().split())

def gcd(x, y):
                if y == 0:
                                return x
                else:
                                x %= y  # xをyで割った余りをxに代入。
                                x, y = y, x  # xとyの中身を入れ換え。
                                return gcd(x, y)
print(gcd(a, b))


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

int main(){
  int n, t, a;
  cin >> n >> t >> a;
  int index = 0, h;
  double T;
  double ans = 1000;
  for( int i = 0; i < n; i++ ) {
    cin >> h;
    T = t - h * 0.006;
    if( abs( T - a ) < ans ) {
      ans = abs( T - a );
      index = i;
    }
  }
  cout << index + 1 << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    string N;
    cin>>N;
    int A= N.at(0)-'0';
    int B= N.at(1)-'0';
    int C= N.at(2)-'0';
    int D= N.at(3)-'0';
    if(A+B+C+D==7){
        cout<<A <<'+'<< B <<'+'<< C<< '+'<< D <<'='<< 7<<endl;
    }
   else if(A+B+C-D==7){
        cout<<A<< '+'<< B<< '+'<< C <<'-' <<D<< '='<< 7<<endl;
    }
    else if(A+B-C+D==7){
        cout<<A<< '+'<< B <<'-'<< C <<'+'<< D <<'=' <<7<<endl;
    }
 else if(A+B-C-D==7){
        cout<<A <<'+'<< B<< '-'<< C <<'-'<< D<< '='<< 7<<endl;
    }
     else if(A-B+C+D==7){
        cout<<A <<'-'<< B <<'+' <<C <<'+'<< D <<'='<< 7<<endl;
    }
   else  if(A-B+C-D==7){
        cout<<A <<'-'<< B <<'+'<< C <<'-' <<D<< '=' <<7<<endl;
    }
    else if(A-B-C-D==7){
        cout<<A <<'-' <<B <<'-'<< C <<'-' <<D<<'='<< 7<<endl;
    }
    else if(A-B-C+D==7){
        cout<<A <<'-'<< B <<'-'<< C <<'+' <<D <<'=' <<7<<endl;
    }

}

Measured memory_bytes: 3628
n = int(input())
s = []
for _ in range(n) :
        s.append(str(input()))
m = int(input())
t = []
for _ in range(m) :
        t.append(str(input()))
ans = 0
for i in s :
        ans = max(ans, s.count(i) - t.count(i))
if ans < 0 :
        ans == 0
print(ans)

Measured memory_bytes: 3064
N = int(input())
X = list(map(int, input().split()))

Y = sorted(X)

for i in range(N):
    if X[i] <= Y[N // 2 - 1]:
        print(Y[N // 2])
    elif X[i] >= Y[N // 2]:
        print(Y[N // 2 - 1])

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

struct Node {
    int key;
    struct Node *right, *left, *parent;
};
typedef struct Node Node;

Node *root, *NIL;

void insert(int k) {
    Node *y = NIL;
    Node *x = root;
    Node *z;
    
    z = (Node *)malloc(sizeof(Node));
    z->key   = k;
    z->left  = NIL;
    z->right = NIL;
    
    while(x != NIL) {
        y = x;
        if(z->key < x->key) {
            x = x->left;
        } else {
            x = x->right;
        }
    }
    
    z->parent = y;
    if(y == NIL) {
        root = z;
    } else {
        if( z->key < y->key) {
            y->left = z;
        } else {
            y->right = z;
        }
    }
}

void inorder(Node *u) {
    if(u == NIL) return;
    inorder(u->left);
    printf(" %d",u->key);
    inorder(u->right);
}
void preorder(Node *u) {
    if(u == NIL) return;
    printf(" %d",u->key);
    preorder(u->left);
    preorder(u->right);
}
    
int main(void) {
    int n, i, x;
    char com[16];
    scanf("%d",&n);
    
    for(i=0;i<n;i++) {
        scanf("%s",com);
        if(!strcmp(com,"insert")) {
            scanf("%d",&x);
            insert(x);
        } else if(!strcmp(com,"print")) {
            inorder(root);
            printf("\n");
            preorder(root);
            printf("\n");
        }
    }

    return 0;
}


Measured memory_bytes: 25156
using System;

class Program
{
    static void Main(string[] args)
    {
        var n = int.Parse(Console.ReadLine());
        var a = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

        var x = 0;
        for (int i = 0; i < n; i++) x += a[i];

        for (int i = 1; i < n; i += 2) x -= 2 * a[i];

        for (int i = 0; i < n; i++)
        {
            Console.WriteLine(x);
            x = 2 * a[i] - x;
        }
    }
}


Measured memory_bytes: 29788
#include <bits/stdc++.h>
const int INF=1e9,MOD=1e9+7;
const long long LINF=1e18;
using namespace std;
#define int long long
//template

//main
signed main(){
  string s;cin>>s;
  int N=15-s.size();
  int win=8-N;
  for(char p:s)if(p=='o')win--;
  if(win<=0)cout<<"YES"<<endl;
  else cout<<"NO"<<endl;
}


Measured memory_bytes: 256
#include<iostream>
#include <string>
#include<math.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)

long long power(int x,int d){
  long long ans=1;
  rep(i,d)ans*=x;
  return ans;
}

void solve(){
  string s;
  cin>>s;
  long long ans=(long long)stoll(s);
  int D=int(log10(ans));
  int j;
  for(int bits=1;bits<(1<<D);bits++){
    ans+=stoll(s)%10;
    j=1;
    for(int i=0;i<D;i++){
      if ((bits>>i)&1)j=0;
      ans+=((long long)s[D-i-1]-48)*power(10,j);
      j++;
    }
  }
  cout<<ans<<endl;
  return;
}

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

Measured memory_bytes: 256
#include <iostream>
#include<map>
#include <algorithm>
#include <vector>
#include <string>
#include <utility>
#include <queue>
#define INF 1e9+7
#define rep(i,n) for(int i=0;i<n;i++)
#define NO cout<<"NO"<<endl;
#define YES cout << "YES"<<endl;
#define No cout << "No"<<endl;
#define Yes cout << "Yes"<<endl;
#define all(a) a.begin(),a.end()
#define P pair<int,int>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

//(int)'a'は97 (int)'A'は65 (int)'1'は49
//おまじない

int main(){
    
    string s;
    char c;
    int n,k;
    cin >> n;
    cin >> s;
    cin>> k;
    c=s[k-1];
    rep(i,n){
        if(s[i]!=c)s[i]='*';
    }
    
    cout << s<<endl;
    
    return 0;
}


Measured memory_bytes: 256
from math import gcd

k = int(input())
range(1, k+1)

l1 = range(1, k+1)
def loop(s):
    for a in l1:
        for b in l1:
            for c in l1:
                l2 = (a, b, c)
                g1 = gcd(a,b)
                g2 = gcd(g1, c)
                s += g2
    return s

print(loop(0))

Measured memory_bytes: 9196
def resolve():
    N, M = list(map(int, input().split()))
    AB = [list(map(int, input().split())) for i in range(M)]
    import collections
    d = collections.OrderedDict([(i, 0) for i in range(1, N+1)])
    for ab in AB:
        d[ab[0]] += 1
        d[ab[1]] += 1
    for k in d:
        print(d[k])


if '__main__' == __name__:
    resolve()

Measured memory_bytes: 3316
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <numeric>
#include <iomanip>
#include <tuple>

using namespace std;
int o[100005];
int e[100005];

int main(){
   int n;
   cin>>n;
   vector<int> v(n);
   for(int i=0;i<n;i++)cin>>v[i];

   int ans=0;
   for(int i=0;i<n;i++){
      if(i%2==0)e[v[i]]++;
      else o[v[i]]++;
   }
   ans=n-(*max_element(e,e+100005)+*max_element(o,o+100005));
   if(max_element(e,e+100005)-e==max_element(o,o+100005)-o){
      sort(e,e+100005,greater<int>());
      sort(o,o+100005,greater<int>());
      ans=n-max(e[0],o[0])-max(e[1],o[1]);
   }
   if(*max_element(v.begin(),v.end())==*min_element(v.begin(),v.end()))ans=n/2;
   cout<<ans<<endl;
}

   


Measured memory_bytes: 1408
from sys import stdin
from itertools import permutations as per
def check(queen):
    for r1, c1 in queen:
        if not all((r1 == r2 and c1 == c2) or (r1 + c1 != r2 + c2 and r1 - c1 != r2 - c2) for r2, c2 in queen):
            return False
    return True
k = int(stdin.readline())
R, C = [[i for i in range(8)] for _ in range(2)]
q = []
for _ in range(k):
    r, c = map(int, stdin.readline().split())
    q.append((r, c))
    R.remove(r)
    C.remove(c)
for l in per(C):
    q_tmp = q[:] + [(r, c) for r, c in zip(R, l)]
    if check(q_tmp):
        for i, j in sorted(q_tmp):
            print("." * j + "Q" + "." * (8 - j - 1))
        break

Measured memory_bytes: 7784
#include <bits/stdc++.h>
#define ROOP(i, N) for(int i=0; i++; i<N)
#define RVROOP(i, N) for(int i=N; i--; i>=0)
#define ALL(v) v.begin(), v.end()
const int INF = 1e9;
const int MAX = 510000;
const int MOD = 1000000007;
using namespace std;
typedef long long ll;

/*DP使ったほうがよくない？？WOWWOW*/

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

  int N; cin>>N;

  for(int i=0; i<N; i++){
    int b; cin>>b;
    for(int j=0; j<3; j++){
      for(int k=0; k<3; k++){
        if(a[j][k]==b){
          a[j][k]*=-1;
        }
      }
    }
  }
  
  bool ans=false;

  for(int i=0; i<3; i++){
    if(a[i][0]<0 && a[i][1]<0 && a[i][2]<0){
      ans=true;
      break;
    }
  }

  if(!ans){
    for(int i=0; i<3; i++){
      if(a[0][i]<0 && a[1][i]<0 && a[2][i]<0){
        ans=true;
        break;
      }
    }
  }

  if(!ans && a[0][0]<0 && a[1][1]<0 && a[2][2]<0){
    ans=true;
  }
  if(!ans && a[0][2]<0 && a[1][1]<0 && a[2][0]<0){
    ans=true;
  }

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

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include <vector>
#include<math.h>
#include <algorithm>
using namespace std;

int main()
{
	int N,C=0;
	cin >> N;
	vector<char> d(N);
	string str;

	for(int i=0;i<N;i++)
		cin >> d[i];

	str += d[0];

	for (int i = 1; i < N; i++)
	{

		if (d[i-1] != d[i])
		{
			str += d[i];

		}
	}
	C = str.size();
	cout << C;

	return 0;
}


Measured memory_bytes: 512
// Best practice
    
    #include<bits/stdc++.h>
    #include <ext/pb_ds/assoc_container.hpp> // Common file 
    #include <ext/pb_ds/tree_policy.hpp> 
    #include <ext/pb_ds/detail/standard_policies.hpp>
    #include <functional> // for less 
    
    #define int         long long
    #define pb          emplace_back
    #define pf          emplace_front
    #define all(a)      (a).begin(),(a).end()
    #define rall(a)     (a).rbegin(),(a).rend()
    #define x           first
    #define y           second
    #define endl        '\n'
    #define tezz        ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    using namespace std;
    using namespace __gnu_pbds; 
     
    typedef tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag, tree_order_statistics_node_update> pbds; 
    
    #define fbo find_by_order
    #define ook order_of_key
    
    signed main() {
       tezz
       
       int n;
       map<string,int> mp;
       cin >> n;
       string s;
       for(int i=0; i<n; i++){
           cin >> s;
           mp[s]++;
       }
       int mx=INT_MIN;
       for(auto it: mp){
           if(it.y>mx){
               mx=it.y;
           }
       }
       for(auto it: mp){
           if(it.y==mx){
               cout << it.x << endl;
           }
       }
    //   cout << ans << endl;
      
       return 0;
    }
    


Measured memory_bytes: 23808
#include<iostream>
#include<string>
using namespace std;
int p[7];
int North(){
  int mem;
  mem = p[1];
  p[1] = p[2];
  p[2] = p[6];
  p[6] = p[5];
  p[5] = mem;
  return p[1];
}
int East(){
  int mem;
  mem = p[1];
  p[1] = p[4];
  p[4] = p[6];
  p[6] = p[3];
  p[3] = mem;
  return p[1];
}
int West(){
  int mem;
  mem = p[1];
  p[1] = p[3];
  p[3] = p[6];
  p[6] = p[4];
  p[4] = mem;
  return p[1];
}
int South(){
  int mem;
  mem = p[1];
  p[1] = p[5];
  p[5] = p[6];
  p[6] = p[2];
  p[2] = mem;
  return p[1];
}
int Right(){
  int mem;
  mem = p[2];
  p[2] = p[3];
  p[3] = p[5];
  p[5] = p[4];
  p[4] = mem;
  return p[1];
}
int Left(){
  int mem;
  mem = p[2];
  p[2] = p[4];
  p[4] = p[5];
  p[5] = p[3];
  p[3] = mem;
  return p[1];
}
int main(){
  int n;
  string com;
  while(cin >> n){
    if(n==0) break;
    int s = 1;
    for(int i=0;i<=6;i++) p[i] = i;
    for(int i=0;i<n;i++){
      cin >> com;
      if(com=="North") s += North();
      else if(com=="East") s += East();
      else if(com=="West") s += West();
      else if(com=="South") s += South();
      else if(com=="Right") s += Right();
      else s += Left();
    }
    cout << s << endl;
  }
  return 0;
}

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

#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<int,int> Pi;


int main(){
  ll h, n;
  cin >> h >> n;
  
  vector<P> p(n);
  rep(i,0,n){
    cin >> p.at(i).fi >> p.at(i).se;
  }
  
  vector<ll> dp(h+1, INT_MAX);
  dp[0] = 0;
  
  rep(i,0,h+1){	//dp[1]〜dp[h]の更新
    rep(j,0,n){	
      int label = min(h, i + p.at(j).fi);
      dp[label] = min(dp[label], dp[i] + p.at(j).se);
      //cout << i << " " << label << " " << dp[label] << endl;
    }
  }
  
  /*rep(i,0, h+1)
    cout << i << " " << dp[i] <<endl;*/
  cout << dp[h] << endl;
}

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

int main() {
    int a, b, c, x, count = 0;
    cin >> a >> b >> c >> x;
    rep(i, a) rep(j, b) rep(k, c) if(500 * i + 100 * j + 50 * k == x) count++;
    cout << count << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define LL long long
#define db long double

using namespace std;
const int N=4000+10;
int rd()
{
    int x=0,w=1;char ch=0;
    while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+(ch^48);ch=getchar();}
    return x*w;
}
int st[N],tp,an[N];
char cc[2];
int qry(int x,int y)
{
    printf("? %d %d\n",x,y),fflush(stdout);
    scanf("%s",cc);
    return cc[0]=='Y';
}

int main()
{
///qlg
    int a=rd(),b=rd(),n=a+b;
    if(a<=b){puts("Impossible");exit(0);}
    for(int i=0;i<n;++i)
    {
	if(!tp) st[++tp]=i;
	else if(qry(st[tp],i)) st[++tp]=i;
	else --tp;
    }
    int smy=st[tp];
    for(int i=0;i<n;++i) an[i]=qry(smy,i);
    printf("! ");
    for(int i=0;i<n;++i) printf("%d",an[i]);
    exit(0);
}

Measured memory_bytes: 724
#include <bits/stdc++.h>
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define RFOR(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define rep(i,n) FOR(i,0,(n))
#define REPS(i,n) FOR(i,1,(n)+1)
#define RREP(i,n) RFOR(i,0,(n))
#define ALL(x) (x).begin(),(x).end()
#define RALL(x) (x).rbegin(),(x).rend()
#define DEBUG(x)  cout << #x << " = " << (x) << endl;
#define SORT(x) sort(ALL(x));
#define RSORT(x) sort(RALL(x));
#define SUM(x) accumulate(ALL(x),0);
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;
const ll mod = 1e9+7;
const int INF = (1<<30)-1;
const ll INFLL = (1LL<<62)-1;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
//cout << fixed << setprecision(10);

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

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

int dp[5005][5005];

int main () {
  int n;
  string s;
  cin >> n >> s;
  
  for (int i = n-1; i >= 0; --i) {
    for (int j = n-1; j >= 0; --j) {
      if (s[i] != s[j]) dp[i][j] = 0;
      else dp[i][j] = dp[i+1][j+1]+1;
    }
  }

  int ans = 0;
  rep(i,n) {
    rep(j,n) {
      if (i >= j) continue; // i < j;
      int now = min(dp[i][j], j-i);
      ans = max(ans, now);
    }
  }

  cout << ans << endl;
}

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

const int maxn = 200005;

int a[maxn], pos[maxn];

int main() {
    int n; cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        pos[a[i]] = i;
    }
    int mx = 1, now = 0, np = 0;
    for (int i = 1; i <= n; ++i) {
        if (pos[i] > np) {
            ++now;
            mx = max(mx, now);
            np = pos[i];
        } else {
            now = 1;
            np = pos[i];
        }
    }
    cout << n - mx << endl;
}


Measured memory_bytes: 1920
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repI(i, d, n) for (int i = (d); i < (n); ++i)
#define reps1(i, n) for (int i = 1; i < (n); ++i)
using namespace std;
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; }

using ll = long long;
using P = pair<int, int>;
using Pl = pair<ll, ll>;
using M = map<int, int>;
ll const INF = 1ll<<61;
double pi = 3.141592653589793238;

int main() {
  double w, h, x, y;
  cin >> w >> h >> x >> y;
  cout << w * h / 2 << " " << int((x == w/2) && (y == h/2)) << endl;


  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

int main(){
  int a[100][100],b[100],i,j,n,m;

  scanf("%d %d",&n,&m);

  for(i=0;i<n;i++)
    for(j=0;j<m;j++)
      scanf("%d",&a[i][j]);

  for(i=0;i<m;i++)
    scanf("%d",&b[i]);

  int c[100];

  for(i=0;i<n;i++)
    c[i]=0;

  for(i=0;i<n;i++)
    for(j=0;j<m;j++)
      c[i]+=a[i][j]*b[j];

  for(i=0;i<n;i++)
    printf("%d\n",c[i]);

  return 0;
}

Measured memory_bytes: 1068
#include <stdio.h>
#include <cmath>
#include <bits/stdc++.h>



using namespace std;

typedef vector<int> VI;
typedef vector<string> VS;


//container util
#define SORT(c) sort((c).begin(),(c).end())

//repetition
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)



int main(void){

	int N; cin >> N;
	cout << N/3 << endl;


	return 0;

}


Measured memory_bytes: 256
n=int(input())
x=list(map(int,input().split()))
t=sum(x)/n
s=int(t)
a=min(t-s,s+1-t)
b=0
if a==t-s:
  b=s
else:
  b=s+1
p=0
for i in range(n):
  p+=(x[i]-b)**2
print(p)

Measured memory_bytes: 3060
#include<vector>
#include<queue>
#include<functional>
#include<algorithm>
#include<set>
#include<iostream>

using namespace std;

const int MX = 1<<19;
const int MM = 1000000007;

typedef long long ll;
typedef pair<int,int> pii;

struct Tree{
	pii t[MX*2];
	void update(int A[MX]){
		for(int i = 1; i < MX; i++) t[i+MX] = pii(A[i], i);
		for(int i = MX-1; i >= 1; i--){
			t[i] = min(t[i*2], t[i*2+1]);
		}
	}
	void update(int x, int v){
		x += MX; t[x] = pii(v, x-MX);
		while(x > 1){
			x /= 2;
			t[x] = min(t[x*2], t[x*2+1]);
		}
	}
	pii read(int s, int e){
		pii r = pii(1e9, -1);
		s += MX, e += MX;
		while(s <= e){
			if( s&1 ) r = min(r, t[s++]);
			if(~e&1 ) r = min(r, t[e--]);
			s /= 2, e /= 2;
		}
		return r;
	}
} tree;

vector<int> G[MX];
int A[MX], B[MX], C[MX], D[MX];
int N, K;

void make_dag(int s, int e, int v = -1){
	if( s > e ) return;
	pii t = tree.read(s, e);
	if( t.second == -1 ) return;
	if( v != -1 && v+K > t.first) G[t.first].push_back(v);
	make_dag(t.second+1, e, v);
}

int main()
{
	scanf("%d%d", &N, &K);
	for(int i = 1; i <= N; i++){
		scanf("%d", B+i);
		A[B[i]] = i;
	}
	tree.update(A);
	for(int i = 1; i <= N; i++){
		make_dag(1, B[i]-1, i);
		tree.update(B[i], 1e9);
	}
	int cnt[MX] = {};
	for(int i = 1; i <= N; i++){
		for(int c : G[i]){
			cnt[c]++;
		}
	}
	priority_queue<int, vector<int>, greater<int>> Q;
	vector<int> ans;
	for(int i = 1; i <= N; i++) if( cnt[i] == 0 ) Q.push(i);
	while(Q.size()){
		int p = Q.top(); Q.pop();
		ans.push_back(p);
		for(int c : G[p]){
			cnt[c]--;
			if( cnt[c] == 0 ) Q.push(c);
		}
	}
	for(int i = 0; i < ans.size(); i++) D[ans[i]] = i+1;
	for(int i = 1; i <= N; i++) printf("%d\n", D[i]);
}


Measured memory_bytes: 75632