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

#define debug(n) cerr << #n << ':' << n << endl;

using namespace std;

using ll = long long;

template<class T,class U>
using umap = unordered_map<T,U>;

template<class T>
using uset = unordered_set<T>;

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

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


int main(){
  string s,t;cin >> s >> t;
  int cnt = 0;
  for(int i = 0; i < 3; ++i)
    if(s[i] == t[i])cnt++;
  cout << cnt << endl;
  return 0;
}


Measured memory_bytes: 256
def print_list(A):
    print(*A, sep=" ")

def swap(a, b):
    return b, a

def find_minj(A, i, n):
    minj = i
    for j in range(i, n):
        if A[j] < A[minj]:
            minj = j
    return minj

def selection_sort(A, n):
    replace_num = 0
    for i in range(0, n):
        minj = find_minj(A, i, n)
        if A[i] > A[minj]:
            A[i], A[minj] = swap(A[i], A[minj])
            replace_num += 1
    print_list(A)
    print(replace_num)

n = int(input())
A = list(map(int,input().split()))

selection_sort(A, n)


Measured memory_bytes: 5608
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.nio.charset.StandardCharsets;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException {
		InputStreamReader reader = new InputStreamReader(System.in, StandardCharsets.UTF_8);
		BufferedReader in = new BufferedReader(reader);
		String[] tokens = in.readLine().split(" ");
		in.close();
		long r = Long.parseLong(tokens[0]);
		long D = Long.parseLong(tokens[1]);
		long x = Long.parseLong(tokens[2]);

		for (int i = 1; i <= 10; ++i) {
			long result = r * x - D;
			System.out.println(result);
			x = result;
		}
	}
}


Measured memory_bytes: 20948
import std.stdio, std.string, std.range, std.conv, std.array, std.algorithm, std.math, std.typecons;

void main() {
    auto xs = 5.iota.map!(_ => readln.chomp.to!int).array;
    auto cs = xs.map!(x => x % 10).filter!(m => m > 0).array;
    auto m = cs.empty ? 0 : (10 - cs.reduce!min);
    writeln(xs.map!(x => cast(int)(ceil(x * 0.1) * 10)).sum - m);
}



Measured memory_bytes: 256
import java.io.*;
import java.math.BigInteger;
import java.util.*;
import java.util.Stack;

public class Main{
	public static class FastReader {
		BufferedReader br;
		StringTokenizer root;
		
 
		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
 
		String next() {
			while (root == null || !root.hasMoreTokens()) {
				try {
					root = new StringTokenizer(br.readLine());
				} catch (Exception r) {
					r.printStackTrace();
				}
			}
			return root.nextToken();
		}
 
		int nextInt() {
			return Integer.parseInt(next());
		}
 
		double nextDouble() {
			return Double.parseDouble(next());
		}
 
		long nextLong() {
			return Long.parseLong(next());
		}
 
		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (Exception r) {
				r.printStackTrace();
			}
			return str;
		}
	}
	
	public static PrintWriter out = new PrintWriter (new BufferedOutputStream(System.out));
	static int mod = (int) (1e9+7);
	static long cf = 998244353;
    static final int MAX = (int) 1e6;
    public static List<Pair>[] edges;
    public static int[][] parent;
    public static int col = 20;
    public static long[] Bit;
    public static long[] fac,inv;
    public  static int[] prime; 
    public static long[] dp;
	public static FastReader sc = new FastReader();
	public static void main(String[] args) {
	//	Scanner sc = new Scanner(System.in);
 
		int a=sc.nextInt(),b=sc.nextInt();
		double ret=0;
		for(int i=1;i<=a;i++){
		double tmp=1.0/a;
		int now=i;
		while(now<b){
		now*=2;
		tmp/=2;
		}
		ret+=tmp;
		}
		out.printf("%.12f\n",ret);
	 
		 
		out.close();
	}

	
	static class Pair{
		int x;
		int y;
		Pair(int x,int y){
			this.x = x;
			this.y = y;
		}
	}
	
}

Measured memory_bytes: 21332
from collections import defaultdict
N, M = map(int, input().split())
A = list(map(int, input().split()))

ans = 0
hash = defaultdict(int)
hash[0] = 1
i = 0
for a in A:
    i = (i+a) % M
    hash[i] += 1
for h in list(hash.keys()):
    ans += hash[h] * (hash[h]-1) // 2

print(ans)

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

#define ll long long
#define sd(x) scanf("%d", &(x))
#define pii pair<int, int>
#define F first
#define S second

#define TRACE

#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
	cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
	const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
const int N = 1e6 + 3, mod = 1e6 + 3;
int fact[N], invfact[N];
inline int add(int x, int y){ x += y; if(x >= mod) x -= mod; return x;}
inline int sub(int x, int y){ x -= y; if(x < 0) x += mod; return x;}
inline int mul(int x, int y){ return (((ll) x) * y) % mod;}
inline int powr(int a, ll b){
	int x = 1 % mod;
	while(b){
		if(b & 1) x = mul(x, a);
		a = mul(a, a);
		b >>= 1;
	}
	return x;
}
inline int inv(int a){ return powr(a, mod - 2);}
void pre(){
	fact[0] = invfact[0] = 1;
	for(int i = 1;i < N; i++) fact[i] = mul(i, fact[i - 1]);
	invfact[N - 1] = inv(fact[N - 1]);
	for(int i = N - 2; i >= 1; i--) invfact[i] = mul(invfact[i + 1], i + 1);
	assert(invfact[1] == 1);
}

inline int C(int n, int k){
	if(n < k || k < 0) return 0;
	return mul(fact[n], mul(invfact[k], invfact[n - k]));
}

inline int getProd(int x, int y){
	if(x == 0) return 0;
	int num = y / mod - (x - 1) / mod;
	if(num) return 0;
	return mul(invfact[(x-1) % mod], fact[y % mod]);
}
int main(){
	pre();
	int q;
	sd(q);
	while(q--){
		int n, x, d;
		sd(x); sd(d); sd(n);
		if(d == 0) printf("%d\n", powr(x, n));
		else{
			x = mul(x, inv(d));
			printf("%d\n", mul(powr(d, n), getProd(x, x + n - 1)));
		}
	}
}

Measured memory_bytes: 8704
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>
#define vv(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define vvi vector<vector<int> >
#define vvl vector<vector<ll> >
#define vll vector<ll>
#define rep(c, a, b) for(ll c=a;c<b;c++)
#define re(c, b) for(ll c=0;c<b;c++)
typedef long long int ll;
typedef long double ld;
using namespace std;

int main(int argc, char const *argv[]) {
  string s;std::cin >> s;
  ll l = 0, r = s.size()+1;
  while(r-l>1){
    ll mid = (l+r)/2;
    ll y = mid-1, x = s.size()-mid;
    bool flag = true;
    for(int i=x; i<=y;i++) if(s[i]!=s[x]) flag = false;
    if(flag) l = mid;
    else r = mid;
  }
  std::cout << l << '\n';
  return 0;
}


Measured memory_bytes: 512
#define _USE_MATH_DEFINES
#define INF 0x3f3f3f3f
#include <iostream>
#include <cstdio>
#include <sstream>
#include <cmath>
#include <cstdlib>
#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;

static const double EPS = 1e-8;

string red_str;
string green_str;
string pak_str;

class State{
public:
  string green;
  string red;
  char mid;
  int upper_idx;
  int left_idx;
  State(int _u,int _l,char _m) : upper_idx(_u),left_idx(_l),mid('.'){}
  bool operator ==(const State& s) const{
    return (green==s.green
	    && red == s.red
	    && mid == s.mid
	    && upper_idx == s.upper_idx
	    && left_idx == s.left_idx);
  }
  bool operator !=(const State& s) const{
    return !(green==s.green
	     && red == s.red
	     && mid == s.mid
	     && upper_idx == s.upper_idx
	     && left_idx == s.left_idx);
  }
};

State push_right(const State& s){
  State next = s;
  if(s.mid != '.') next.green.push_back(s.mid);
  if(s.left_idx < green_str.size()){
    next.mid = green_str[s.left_idx];
    next.left_idx = s.left_idx+1;
  }
  else{
    next.mid = '.';
  }
  return next;
}

State push_down(const State& s){
  State next = s;
  if(s.mid != '.') next.red.push_back(s.mid);
  if(s.upper_idx < red_str.size()){
    next.mid = red_str[s.upper_idx];
    next.upper_idx = s.upper_idx+1;
  }
  else{
    next.mid = '.';
  }
  return next;
}

int main(){
  while(cin >> red_str){
    if(red_str == "-") break;

    cin >> green_str;
    cin >> pak_str;

    State state(0,0,-1);

    for(int round =0; round < 1000;round++){
      if(state.mid != -1){
	bool has_pak = false;
	for(int i=0;i<pak_str.size();i++){
	  if(state.mid == pak_str[i]){
	    has_pak = true;
	  }
	}
	if(has_pak){
	  state = push_down(state);
	}
	else{
	  state = push_right(state);
	}
      }
      else{
	State prev = state;
	state = push_down(state);
	if(prev == state) break;
      }
    }

    cout << state.green << endl;
  }
}

Measured memory_bytes: 1192
import sys

n, y = map(int, input().split())

for i in range(n + 1):
    for j in range(n + 1):
        if 0 <= n - i - j <= n and i * 10000 + j * 5000 + (n - i - j) * 1000 == y:
            print(" ".join(map(str, [i, j, n - i - j])))
            sys.exit()
print("-1 -1 -1")

Measured memory_bytes: 40940
# 入力
import sys
stdin = sys.stdin

def li(): return [int(x) for x in stdin.readline().split()]
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return [float(x) for x in stdin.readline().split()]
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(ns())
def nf(): return float(ns())


s = ns()
a = s.count("a")
b = s.count("b")
c = s.count("c")

if max(a,b,c) - min(a,b,c) <= 1:
    print("YES")
else:
    print("NO")


Measured memory_bytes: 3188
#include <bits/stdc++.h>
#define REP(i, x, y) for (ll i = x; i <= y; i++)
#define BIT(t) (1ll << t)
#define PER(i, y, x) for (ll i = y; i >= x; i--)
#define vll vector<ll>
#define vvll vector<vector<ll>>
#define pll pair<ll, ll>
#define SIZE(v) ll(v.size())
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());
using namespace std;
typedef long long ll;
//        ios::sync_with_stdio(false);
//        cin.tie(nullptr);

int main(){
  string s;
  cin >> s;
  REP(i,0,SIZE(s)-1){
    if(s[i] == '?'){
      s[i]  = 'D';
    }
  }
  cout << s << endl;
}

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

int main() {
  string s; cin >> s;
  for(int i = 0; i < (int)s.size() - 1; i++) if(s[i] == s[i + 1]) return puts("Bad"), 0;
  cout << "Good";
  return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	static Scanner scanner;
	public static void main(String[] args) {
	    scanner = new Scanner(System.in);

        int h=gi();
        int a=gi();
        
	    
	    
        System.out.println((int)Math.ceil((double)(h+a)/2));
//        if (xo>w || yo>h) {
//        	System.out.print(0);
//        }else {
//        	System.out.print((h-yo)*(w-xo));
//        }


	}

	// 文字列として入力を取得
	public static String gs() {
		return scanner.next();
	}

	// intとして入力を取得
	public static int gi() {
		return Integer.parseInt(scanner.next());
	}

	// longとして入力を取得
	public static long gl() {
		return Long.parseLong(scanner.next());
	}
	
	// doubleとして入力を取得
	public static double gd() {
		return Double.parseDouble(scanner.next());
	}
}

Measured memory_bytes: 35692
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;

int main()
{
	int n,j,k,a[10009],m=0;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
	}
	sort(a,a+n);
	for(int i=0;i<n-2;i++)
	{
		for(j=i+1;j<n-1;j++)
		{
			for(k=j+1;k<n;k++)
			{
				if(a[i]<a[j]+a[k]&&a[j]<a[k]+a[i]&&a[k]<a[i]+a[j])
				{
					m++;
				}
				else
				{
					break;
				}
			}
		}
	}
	cout<<m;
	return 0;
 } 

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

using namespace std;

int gcd(int a, int b){
	return b ? gcd(b, a%b) : a;
}

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

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

	int ans = a[0];

	for (int i = 1; i < n; i++)
		ans = gcd(ans, a[i]);

	cout << ans << endl;

	return 0;
}


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

using namespace std;

typedef pair<long,long> ll;

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

    vector<ll> rs;
    for (int i = 0; i < n; i++) {
        long xi, li;
        cin >> xi >> li;
        rs.emplace_back(xi-li, xi+li);
    }

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

    int lastL = rs[n-1].first;
    int counter = 1;
    for (int i = n-2; i >= 0; i--) {
        if (rs[i].second <= lastL) {
            lastL = rs[i].first;
            counter++;
        }
    }

    cout << counter << endl;

    return 0;
}


Measured memory_bytes: 2420
fn main() {
    let t: usize = {
        let mut buf = String::new();
        std::io::stdin().read_line(&mut buf).unwrap();
        buf.trim_end().parse().unwrap()
    };

    for _ in 0..t {
        let n: usize = {
            let mut buf = String::new();
            std::io::stdin().read_line(&mut buf).unwrap();
            buf.trim_end().parse().unwrap()
        };
        let mut l: Vec<isize> = Vec::with_capacity(n);
        let mut r: Vec<isize> = Vec::with_capacity(n);
        let (mut left, mut right) = (Vec::new(), Vec::new());
        for i in 0..n {
            let mut buf = String::new();
            std::io::stdin().read_line(&mut buf).unwrap();
            let mut iter = buf.split_whitespace();
            let k: usize = iter.next().unwrap().parse().unwrap();
            l.push(iter.next().unwrap().parse().unwrap());
            r.push(iter.next().unwrap().parse().unwrap());
            if l[i] > r[i] {
                left.push((k, i));
            } else {
                right.push((n - k, i));
            }
        }

        let mut ans = 0;
        {
            left.sort();
            let mut heap = std::collections::BinaryHeap::new();
            for (k, i) in left {
                if heap.len() < k {
                    ans += l[i];
                    heap.push(r[i] - l[i]);
                } else {
                    let &x = heap.peek().unwrap();
                    if x > r[i] - l[i] {
                        ans += x;
                        heap.pop();
                        ans += l[i];
                        heap.push(r[i] - l[i]);
                    } else {
                        ans += r[i];
                    }
                }
            }
        }
        {
            right.sort();
            let mut heap = std::collections::BinaryHeap::new();
            for (k, i) in right {
                if k == 0 {
                    ans += l[i];
                } else if heap.len() < k {
                    ans += r[i];
                    heap.push(l[i] - r[i]);
                } else {
                    let &x = heap.peek().unwrap();
                    if x > l[i] - r[i] {
                        ans += x;
                        heap.pop();
                        ans += r[i];
                        heap.push(l[i] - r[i]);
                    } else {
                        ans += l[i];
                    }
                }
            }
        }
        println!("{}", ans);
    }
}

Measured memory_bytes: 9548
from itertools import product
from functools import lru_cache
n = int(input())
mod = 10**9+7
condition = True

@lru_cache(64*n)
def func(tpl, count) :
    if tpl in (("A","G","C"), ("A","C","G"), ("G","A","C")) :
        return 0
    if count :
        count -= 1
        if tpl[1:] == ("A","G") :
            return sum(func(("A","G",c), count) for c in "AGT")%mod
        if tpl[1:] == ("A","C") :
            return sum(func(("A","C",c), count) for c in "ACT")%mod
        if tpl[1:] == ("G","A") :
            return sum(func(("G","A",c), count) for c in "AGT")%mod
        if tpl[:2] == ("A","G") :
            return sum(func(tpl[1:]+(c,), count) for c in "AGT")%mod
        if tpl[0]+tpl[2] == "AG" :
            return sum(func(tpl[1:]+(c,), count) for c in "AGT")%mod
        return sum(func(tpl[1:]+(c,), count) for c in "ACGT")%mod
    return 1

ans = 0
for firstthree in product("ACGT", repeat=3) :
    ans = (ans+func(firstthree, n-3))%mod
print(ans)

Measured memory_bytes: 6384
fun main(args: Array<String>) {
    val N = readLine()!!.toInt()
    val list = Array(N) {
        readLine()!!.split(" ").map(String::toInt)
    }

    val dp = Array(N + 1) { Array(3) { 0 } }
    for (i in 1..N) {
        // LISTの添字
        val n = i - 1
        // 今日
        for (j in 0 until 3) {
            // 前日　
            for (k in 0 until 3) {
                if (j == k) {
                    continue
                }
                dp[i][j] = Math.max(dp[i][j], dp[i - 1][k] + list[n][j])
            }
        }
    }

    println(dp[N].max())
}

Measured memory_bytes: 95788
#include <bits/stdc++.h>
#include <cassert>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
struct Edge
{
  int to;
  int weight;
  Edge(int t, int w) : to(t), weight(w) {}
};
using Graph = vector<vector<Edge>>;
// using Graph = vector<vector<int>>;

const long long INF = 1LL << 60;
const int INT_INF = 1000000000;

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

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int N;
  cin >> N;
  int x = 800 * N;
  int y = N / 15 * 200;
  cout << x - y << endl;
  return 0;
}


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

int main() {
	long long int k,a,b,zan;
  	cin>>k>>a>>b;
  	//ビスケットをたたき続けたほうがいい場合
  	if((a+2)>=b){
    	cout<<k+1<<endl;
      	return 0;
    }
  	//ビスケットを交換するにいたらない場合
  	if(k<=a){
    	cout<<k+1<<endl;
      	return 0;
    }
  	//ビスケットを交換する場合
    //交換軌道に乗るまでに何回操作するのか？
    zan=k-a+1;
    if(zan%2==0){
    	cout<<a+zan/2*(b-a)<<endl;
    }else{
    	cout<<a+zan/2*(b-a)+1<<endl;
    }
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <functional>
#include <numeric>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cassert>
#define bogo_sort   std::sort
#define bozo_sort   std::stable_sort
#define alles(obj)  obj.begin(), obj.end()
#define elif        else if
#define unless(flg) if(!(flg))
#define elless(flg) else if(!(flg))
#define echo        std::cout <<
#define read        std::cin >>
#define endl        std::endl
#define fin         << '\n'
#define bash        push_back
#define makePair    std::make_pair
#define _           << ' ' <<
// type-define
#define Stack       std::stack
#define Queue       std::queue
#define Set         std::set
#define PQueue      std::priority_queue
#define Vector      std::vector
#define Pair        std::pair
#define Map         std::map
#define HashMap     std::unordered_map
#define Greater     std::greater
using String  =     std::string;
using llong   =     long long;
using boolean =     bool;
using Pii     =     Pair<int, int>;
using Vi      =     Vector<int>;
using Vii     =     Vector<Pii>;
// utils
constexpr int   dx[] = {1, 0, -1, 0, 1, 1, -1, -1};
constexpr int   dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
constexpr int   INF  = 0x3f3f3f3f;
constexpr llong LINF = 0x3f3f3f3f3f3f3f3fLL;

namespace {
    template<class A, class B> A power ( llong x, llong n, llong mod ) {
        llong ans = 1;
        while ( n > 0 ) {
            if ( n & 1 ) ans = ( ans * x ) % mod;
            x = ( x * x ) % mod;
            n >>= 1;
        }
        return ans;
    }
    template<class A, class B> A power ( A x, B n ) { return power( x, n, 1000000007 ); }
    template<class A> A gcd ( A x, A y ) { return x % y ? gcd( y, x % y ) : y; }
    template<class A, class B> A lcm   ( A x,  B y ) { return ( x / gcd(x, y) * y ); }
    template<class A> inline A abs ( A n ) { return ( n < 0 ) ? -n : n; }
    template<class A, class B> inline bool chmax ( A &a, const B &b ) { return b > a ? a = b, true : false; }
    template<class A, class B> inline bool chmin ( A &a, const B &b ) { return b < a ? a = b, true : false; }
    boolean isMovable ( int x, int y, int w, int h ) {
        return ( x >= 0 && y >= 0 && x < w && y < h );
    }
}

namespace Rlyeh {

    int n;
    llong a, b;

    signed call_of_Cthulhu( signed datum ) {

        read n;
        read a >> b;
        for ( int i = 1; i < n; i++ ) {
            int A, B;
            read A >> B;
            llong mul = std::max((a+A-1)/A, (b+B-1)/B);
            a = mul * A;
            b = mul * B;
        }

        echo (a+b) fin;

        return 0;
    }
}

signed main(){std::cin.tie(0); std::ios::sync_with_stdio(false); int main_result = Rlyeh::call_of_Cthulhu(114514); return 0;}


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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, K, Q = MAP()
A = LIST()

ans = INF
# 使う要素の最小値とする値xを全探索
for x in A:
    # 数列Aをx未満の値で区切った数列Bを作る
    B = []
    tmp = []
    for i in range(N):
        if A[i] >= x:
            tmp.append(A[i])
        else:
            B.append(tmp)
            tmp = []
    B.append(tmp)
    # 数列B内の各数列から、使える要素を集める
    C =  []
    for li in B:
        m = len(li)
        li.sort()
        C += li[:max(m-K+1, 0)]
    # 集めた要素からQ個をクエリで使うので、小さい方からQ番目が使う要素の最大値y
    C.sort()
    if len(C) < Q:
        continue
    y = C[Q-1]
    ans = min(ans, y - x)
print(ans)


Measured memory_bytes: 53724
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;

int n,m,l,cnt,mx,my;
char a[1009][1009];
int vis[1009][1009];
pair<int,int> p[10],st;
int mov[4][2] = {1,0,0,-1,-1,0,0,1};
struct status
{
    int x,y;
    int ord;
    int fx;
    status(int a,int b,int c,int s)
    {
        x = a, y = b, ord = c, fx = s;
    }
    bool operator < (struct status t) const
    {
        if(ord != t.ord) return ord > t.ord;
        else return fx > t.fx;
    }
};

void bfs(int x,int y,int color)
{
    priority_queue <struct status> q;
    struct status temp(x,y,0,fabs(x-p[color].first) + fabs(y - p[color].second));
    q.push(temp);
    int flag = 0;
    while(!q.empty())
    {
        struct status nw = q.top();
        q.pop();
        if(nw.x == p[color].first && nw.y == p[color].second)
        {
            cnt += nw.ord;
            break;
        }
        vis[nw.x][nw.y] = 1;
        for(int i=0;i<4;i++)
        {
            int tx = mov[i][0] + nw.x, ty = nw.y + mov[i][1];
            if(tx>=0 && tx< n && ty>=0 && ty< m && !vis[tx][ty] && a[tx][ty] != 'X')
            {
                struct status tmp(tx,ty,nw.ord+1,fabs(tx-p[color].first) + fabs(ty - p[color].second));
                q.push(tmp);
                vis[tx][ty] = 1;
            }
        }
    }
}

int main()
{
    while(~scanf("%d%d%d",&n,&m,&l))
    {
        getchar();
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                scanf("%c",&a[i][j]);
                if(a[i][j]>='0' && a[i][j]<='9')
                    p[a[i][j]-'0'].first = i, p[a[i][j]-'0'].second = j;
                if(a[i][j] == 'S') st.first = i, st.second = j;
            }
            getchar();
        }

        int sx = st.first, sy = st.second;
        cnt = 0;
        for(int i=1;i<=l;i++)
        {
            memset(vis,0,sizeof(vis));
            bfs(sx,sy,i);
            sx = p[i].first, sy = p[i].second;
        }
        printf("%d\n",cnt);
    }
    return 0;
}

Measured memory_bytes: 6012
#include<bits/stdc++.h>
using namespace std;
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  long long n, m;
  cin >> n >> m;
  bool mid[n][2];
  for(int i = 0; i < n; i++){
    mid[i][0] = false;
    mid[i][1] = false;
  }
  for(int i = 0; i < m; i++){
    long long a, b;
    cin >> a >> b;
    a--;
    b--;
    if(a == 0) mid[b][0] = true;
    if(b == 0) mid[a][0] = true;
    if(a == n-1) mid[b][1] = true;
    if(b == n-1) mid[a][1] = true;
  }
  for(int i = 0; i < n; i++){
    if(mid[i][0] && mid[i][1]){
      cout << "POSSIBLE" << endl;
      return 0;
    }
  }
  cout << "IMPOSSIBLE" << endl;
  return 0;
}

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

int ar[300];

int main() {
    int n;
    scanf("%d",&n);

    for (int i = 0; i < 2*n; ++i)
    	scanf("%d",&ar[i]);

    stable_sort(ar,ar+2*n,greater<int>());
    int ans = 0;
    for (int i = 1; i < 2*n; i += 2) 
    	ans += ar[i];

    printf("%d\n",ans);
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

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

        int total = 0;

        if(a == 5){
            total += 5;
        }
        if (a == 7){
            total += 7;
        }
        if( b == 5){
            total += 5;
        }
        if ( b == 7){
            total += 7;
        }
        if( c == 5){
            total += 5;
        }
        if ( c == 7){
            total += 7;
        }

        if(total == 17){
            System.out.println("YES");
        }else{
            System.out.println("NO");
        }

    }
}

Measured memory_bytes: 23892
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}

int N,M;

int x[100000],y[100000];

bool o[400][400];
bool no[400];

int main(){
	cin>>N>>M;
	rep(i,M) cin>>x[i]>>y[i],x[i]--,y[i]--;

	rep(i,N){
		o[i][i] = 1;
		for(int j=M-1;j>=0;j--){
			int a = x[j], b = y[j];
			if(o[i][a] && o[i][b]){
				no[i] = 1;
				break;
			}
			if(o[i][a]^o[i][b]) o[i][a] = o[i][b] = 1;
		}
	}

	int ans = 0;

	rep(i,N) rep(j,i){
		if(no[i] || no[j]) continue;
		bool ok = 1;
		rep(x,N) if(o[i][x]&&o[j][x]) ok = 0;
		if(ok) ans++;
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 1152
import java.util.*;

public class Main{
  public static void main(String[]args){
    Scanner sc = new Scanner(System.in);
    String S = sc.nextLine();
    int s = S.length();
    int N = s/2;
    String S1 = "", S2 = "";
    if(s%2 == 0){
      S1 = S.substring(0,N);
      S2 = S.substring(N,s);
    }else{
      S1 = S.substring(0,N);
      S2 = S.substring(N+1, s);
    }
    
    int ans = 0;
    for(int i = 0; i < N; i++){
      if(S1.charAt(i) != S2.charAt(N-i-1)){
        ans++;
      }
    }
    System.out.println(ans);
  }
}

Measured memory_bytes: 23124
#include<bits/stdc++.h>
#include<iomanip>
using namespace std;
typedef long long ll;
typedef long  l;
typedef pair<int,int> P;
#define rep(i,n) for(int i=0;i<n;i++)
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
const double PI=3.14159265358979;
const int INF=1000000007;
const ll LMAX=1000000000000000001;
const ll mod=1000000007;
ll gcd(ll a,ll b){if(a<b)swap(a,b);while((a%b)!=0){a=b;b=a%b;}return b;}
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};

int main(){
  int n,k; cin>>n>>k;
  vector<ll> h(n);
  rep(i,n) cin>>h[i];
  sort(ALL(h));
  ll sum=0;
  rep(i,n-k){
    sum+=h[i];
  }
  cout<<sum<<endl;

  return 0;
}


Measured memory_bytes: 1792
#![allow(non_snake_case, unused_imports)]

// Input
macro_rules! input { (source = $s:expr, $($r:tt)*) => { let mut iter = $s.split_whitespace(); let mut next = || { iter.next().unwrap() }; input_inner!{next, $($r)*} }; ($($r:tt)*) => { let stdin = std::io::stdin(); let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock())); let mut next = move || -> String{ bytes.by_ref().map(|r|r.unwrap() as char).skip_while(|c|c.is_whitespace()).take_while(|c|!c.is_whitespace()).collect() }; input_inner!{next, $($r)*} }; }
macro_rules! input_inner { ($next:expr) => {}; ($next:expr, ) => {}; ($next:expr, $var:ident : $t:tt $($r:tt)*) => { let $var = read_value!($next, $t); input_inner!{$next $($r)*} }; ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => { let mut $var = read_value!($next, $t); input_inner!{$next $($r)*} }; }
macro_rules! read_value { ($next:expr, ( $($t:tt),* )) => { ( $(read_value!($next, $t)),* ) }; ($next:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>() }; ($next:expr, [ $t:tt ]) => { { let len = read_value!($next, usize); (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>() } }; ($next:expr, chars) => { read_value!($next, String).chars().collect::<Vec<char>>() }; ($next:expr, bytes) => { read_value!($next, String).into_bytes() }; ($next:expr, usize1) => { read_value!($next, usize) - 1 }; ($next:expr, $t:ty) => { $next().parse::<$t>().expect("Parse error") }; }

// Module
use std::cmp::{min,max};
use std::collections::{HashSet,HashMap,BTreeMap,VecDeque};

// Functions

// Main
fn main(){
    input!{
        N: usize,
        A: i64,
        B: i64,
        C: i64,
        L: [i64; N]
    }
    let mut ans:i64 = 1<<60;
    for i in 1..1<<2*N{
        let mut a = vec![];
        let mut b = vec![];
        let mut c = vec![];
        let (mut sumA, mut sumB, mut sumC) = (0,0,0);
        for j in 0..N{
            let k = i>>2*j & 3;
            if k==1{
                a.push(L[j]);
                sumA += L[j];
            }else if k==2{
                b.push(L[j]);
                sumB += L[j];
            }else if k==3{
                c.push(L[j]);
                sumC += L[j];
            }
        }
        if a.len()*b.len()*c.len()==0{
            continue;
        }
        let mut x:i64 = 0;
        for l in vec![a.len(), b.len(), c.len()].into_iter(){
            if l>1{
                x += (l-1) as i64 *10;
            }
        }
        x += (A-sumA).abs() + (B-sumB).abs() + (C-sumC).abs();
        ans = min(ans,x);
    }
    println!("{}", ans);
}

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

#define rep(i, n) for(int i=0; i < n; i++)
#define reps(i, n) for(int i=1; i <= n; i++)
#define INF 1e9
#define ALL(v) v.begin(), v.end()

using namespace std;
using ll=long long;

int main() {
  int n,p;
  cin >> n;
  int k = 0;

  rep(i,n){
    cin >> p;
    if(p!=i+1)k++;
  }
  cout << ((k<=2)?"YES":"NO");
}

Measured memory_bytes: 256
#include <stdio.h>
 
int main(void)
{
    int x, y, z;
    int a;
 
    scanf("%d%d%d", &x, &y, &z);
 
    if (x > y)
    {
        a = x;
        x = y;
        y = a;
    }
 
    if (x > z)
    {
        a = x;
        x = z;
        z = a;
    }
 
    if (y > z)
    {
        a = y;
        y = z;
        z = a;
    }
 
    printf("%d %d %d\n", x, y, z);
 
    return 0;
}

Measured memory_bytes: 596
#include <iostream>
#include <cmath>

int main() 
{
  int n,v,j;
  std::cin >> n;
  int A[n] = {0};
  for(int i = 0; i < n; i++) {
    std::cin >> A[i];
  }

  for(int i = 0; i < n; i++) {
    v = A[i];
    j = i - 1;
    while(j >= 0 && A[j] > v) {
      A[j + 1] = A[j];
      j--;
      A[j + 1] = v;
    }
    for(int i = 0; i < n; i++) {
      std::cout << A[i];
      if(i != n - 1) {
	    std::cout << " ";  
      }
    }
    std::cout << "\n";
  }

  return 0;
}



Measured memory_bytes: 3084
#include <bits/stdc++.h>
using namespace std;
#include <math.h>
#include <iomanip>
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; }

const int mod=1000000007;
const int INF=1001001001;

int main() {
  int N;
  cin>>N;
  vector<int>A(N);
  for(int i=0;i<N;i++){
    cin>>A[i];
  }
  int64_t ans=0;
  for(int i=0;i<N;i++){
    ans+=A[i]/2;
    if(i<N-1&&A[i]%2!=0&&A[i+1]!=0){ans++;A[i+1]--;}
  }
  cout<<ans<<endl;
  return 0;  
}

Measured memory_bytes: 3764
#include <bits/stdc++.h>
 
using namespace std;
 
#define FOR(i, n) for(int i = 0; i < (int) n; i++)
#define rall(x) x.rbegin(), x.rend()
#define all(x) x.begin(), x.end()
#define PB push_back
#define F first
#define S second
 
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
 
const ll MOD = 1e9+7;

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

 	ll k = 100;
 	int ans = 0;
 	while(k < x){
 		k = k*(1.01);
 		ans++;
 	}
 	cout << ans << '\n';

	return 0;
}

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


int main(){

    ll N;
    cin >> N;
    std::set<string> s;
    string str;
    for(int i=0;i<N;i++)
    {
        
        cin >> str;
        s.insert(str);
    }

    cout << s.size();

    return 0;
}


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

bool compare_by_b(pair<int, int> a, pair<int, int> b) {
    if(a.second != b.second){
        return a.second > b.second;
    }else{
        return a.first > b.first;
    }
}

int main(){
  int N, M;
  cin >> N >> M;
  
  vector<int> A(N);
  for(int i=0; i<N; i++) cin >> A[i];
  
  vector<pair<int,int>> bc(M);
  for(int i=0; i<M; i++) cin >> bc[i].first >> bc[i].second;
  
  sort(A.begin(), A.end(), greater<int>());
  sort(bc.begin(), bc.end(), compare_by_b);
  
  long long sum=0;
  int count =0;
  int i=0;
  int j=0;
  while(true){
    if(A[i]>bc[j].second){
      sum += A[i];
      i += 1;
      count += 1;
    }else{
      sum += bc[j].second;
      bc[j].first -= 1;
      count += 1;
      if(bc[j].first==0){
        j += 1;
      }
    }
    
    if(count==N) break;
  }
  
  cout << sum << endl;

}

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

L=[]
for i in range(Q):
    a=list(map(int,input().split()))
    L.append(a)
#print(L)
Arr=[]
for i in range(1,M+1):
    Arr.append([i])
#print(Arr)
for n in range(N-1):
    arr=[]
    for i in range(len(Arr)):
        for j in range(Arr[i][-1],M+1):
            arr.append(Arr[i]+[j])
    #print(arr)
    Arr=arr
#print(len(Arr))
ans=0
for i in range(len(Arr)):
    l=[0]+Arr[i]
    cnt=0
    for a,b,c,d in L:
        if l[b]-l[a]==c:
            cnt+=d
    if ans<cnt:
        ans=cnt
print(ans)

Measured memory_bytes: 107572
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <climits>
#include <vector>
#include <map>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>

#define REP(i,n) for(int i=0;i<n;++i)
#define REPR(i,n) for(int i=n;i>=0;--i)
#define REPI(itr,v) for(auto itr=v.begin();itr!=v.end();++itr)
#define REPIR(itr,v) for(auto itr=v.rbegin();itr!=v.rend();++itr)
#define FOR(i,a,b) for(int i=a;i<b;++i)
#define SORT(v,n) sort(v, v+n)
#define SORTV(v) sort(v.begin(), v.end())
#define ALL(v) v.begin(),v.end()
#define llong long long
#define INF 999999999
#define SUR 1000000007
#define pb push_back
#define pf push_front
#define MP make_pair

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

using namespace std;

typedef pair<int,int> pii;

int main(){

  string s;
  while(cin >> s){
    bool f = false;
    REP(i,3){
      int n = i * 3;
      if(s[n] != 's' && s[n] == s[n+1] && s[n] == s[n+2]){
        cout << s[n] << endl;
        f = true;
        break;
      }
      if(s[i] != 's' && s[i] == s[i + 3] && s[i] == s[i + 6]){
        cout << s[i] << endl;
        f = true;
        break;
      }
    }
    if(s[4] != 's' && !f && ((s[0] == s[4] && s[0] == s[8]) || (s[2] == s[4] && s[2] == s[6]))){
      cout << s[4] << endl;
      f = true;
    }
    if(!f){
      cout << "d" << endl;
    }
  }
  return 0;
}




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

int main() {
  int64_t l, r, ans = 0, tmp;
  cin >> l >> r;
  if (l % 2019 == 0 or r % 2019 == 0) ans = 0;
  else {
    ans = (l % 2019) * ((l % 2019)+1);
    for (int i = l; i < r; i++) {
      for (int j = i + 1; j <= r; j++) {
        tmp = ((i%2019) * (j%2019)) % 2019;
        if (tmp < ans) ans = tmp;
        if (ans == 0) {
          cout << "0" << endl;
          return 0;
        }
      }
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<map>
#include<string.h>
#include<complex>
#include<math.h>
#include<queue>
#include <functional>
#include<time.h>
#include <stack>
#include<iomanip>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define ll long long
#define llint long long int
#define reverse(v)  reverse(v.begin(), v.end());
#define Yes(ans) if(ans)cout<<"Yes"<<endl; else cout<<"No"<<endl;
#define YES(ans) if(ans)cout<<"YES"<<endl; else cout<<"NO"<<endl;
#define hei(a) vector<a>
#define whei(a) vector<vector<a>>
#define UF  UnionFind 
#define Pint pair<int,int>
#define keta(a)  fixed << setprecision(a)
constexpr auto INF = 100000000000;
constexpr auto mod = 1000000007;
//辞書順はnext_permutation( begin( v ), end( v ) );やで！
// lower_boundは二分探索
struct edge { int to, cost; };
long long modpow(long long a, long long n, long long mod) {
	long long res = 1;
	while (n > 0) {
		if (n & 1) res = res * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}

// mod. m での a の逆元 a^{-1} を計算するよ！
long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}


//aCbをmod.mで割った余りを求める
ll int c(ll int a, ll int b, ll int m) {
	ll int ans = 1;
	for (ll int i = 0; i < b; i++) {
		ans *= a - i;
		ans %= m;
	}
	for (ll int i = 1; i <= b; i++) {
		ans *= modinv(i, m);
		ans %= m;
	}
	return ans;
}

//sは初めの点、vは頂点size、dは最短距離を求める(初期化はINF),Gは有向グラフ
void dijkdtra(int s, int v, vector<int>& d, whei(edge)& G) {
	priority_queue<Pint, vector<Pint>, greater<Pint>> que;//firstが距離、secondが頂点
	d[s] = 0;//スタートの距離はもちろんzero
	que.push(Pint(0, s));
	while (!que.empty()) {
		Pint p = que.top();
		que.pop();
		int V = p.second;
		if (d[V] < p.first)continue;
		for (int i = 0; i < G[V].size(); i++) {
			edge e = G[V][i];
			if (d[e.to] > d[V] + e.cost) {
				d[e.to] = d[V] + e.cost;
				que.push(Pint(d[e.to], e.to));
			}
		}
	}
}

llint binary_search(vector<int>&s,llint a) {
	llint l = -1;
	llint r = (int)s.size();
	while (r - l > 1) {
		llint mid = l + (r - l) / 2;

		if (s[mid]>=a) r = mid;
		else l = mid;
	}
	return r;
}


int main() {
	llint n;
	cin >> n;
	hei(int) a(n), b(n), c(n);
	rep(i, 0, n)cin >> a[i];
	rep(i, 0, n)cin >> b[i];
	rep(i, 0, n)cin >> c[i];
	sort(a.begin(), a.end());
	sort(b.begin(), b.end());
	sort(c.begin(), c.end());
	llint ans = 0;
	rep(i, 0, n) {
		ans += binary_search(a, b[i])*(n -binary_search(c, b[i]+1));
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1408
#include<iostream>
#include<vector>
using namespace std;
#define inRange(x,a,b) (a <= x && x <= b)

inline int dist(int si, int sj, int gi, int gj){
    return abs(si-gi)+abs(sj-gj);
}

const int INF = 1<<30;

int main(){
    int w, h;
    while(cin >> w >> h, w+h){
        vector<pair<int,int>> vp[5];
        int si, sj, gi, gj;
        char mat[h][w];
        for(int i = 0; i < h; i++){
            for(int j = 0; j < w; j++){
                cin >> mat[i][j];
                if(mat[i][j] == 'S')    si = i, sj = j;
                if(mat[i][j] == 'G')    gi = i, gj = j;
                if(inRange(mat[i][j],'1','5')){
                    vp[mat[i][j]-'1'].push_back({i,j});
                }
            }
        }
        int ans = -1, score = INF;
        for(int i = 0; i < 5; i++){
            vector<vector<int>> dp(4, vector<int>(1000,INF));
            for(int j = 0; j < vp[(i+1)%5].size(); j++){
                dp[0][j] = dist(si,sj,vp[(i+1)%5][j].first,vp[(i+1)%5][j].second);
            }
            for(int j = 0; j < 3; j++){
                int from = (i+1+j)%5, to = (i+1+j+1)%5;
                for(int k = 0; k < vp[from].size(); k++){
                    for(int l = 0; l < vp[to].size(); l++){
                        dp[j+1][l] = min(dp[j+1][l], dp[j][k]+dist(vp[from][k].first, vp[from][k].second, vp[to][l].first, vp[to][l].second));
                    }
                }
            }
            int tmp = INF;
            for(int j = 0; j < vp[(i+4)%5].size(); j++){
                tmp = min(tmp, dp[3][j] + dist(vp[(i+4)%5][j].first, vp[(i+4)%5][j].second, gi, gj));
            }
            if(score > tmp){
                score = tmp;
                ans = i;
            }
        }
        if(score == INF)    cout << "NA" << endl;
        else                cout << ans+1 << " " << score << endl;
    }
    return 0;
}


Measured memory_bytes: 4212
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;

#define vi vector<int>
#define vl vector<long long>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REPD(i, n) for (int i = (int)(n-1); i >= 0; i--)
#define FOR(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define FORD(i, a, b) for (int i = (int)(a); i >= (int)(b); i--)
#define INF 1e18
#define MOD 1e9+7

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

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

const int MAX_N = 110;
const int MAX_W = 10010;
int dp[MAX_N][MAX_W];
int value[MAX_N];
int weight[MAX_N];

int N, W;

void knapsack() {
    dp[0][0] = 0;
    REP(i, N) {
        REP(w, W+1) {
            if (w >= weight[i]) dp[i+1][w] = max(dp[i+1][w-weight[i]]+value[i], dp[i][w]);
            else dp[i+1][w] = dp[i][w];
        }
    }
}
int main() {
    cin >> N >> W;
    REP(i, N) {
        cin >> value[i] >> weight[i];
    }
    knapsack();
    cout << dp[N][W] << endl;
    return 0;
}


Measured memory_bytes: 7000
#include <iostream>
#include <algorithm>
using namespace std;
#define int long long
signed main() {
	int n, m, a[345678], b[345678];
	cin>>n;
	for(int i=0;i<n;i++){cin>>a[i];b[i]=a[i];}
	sort(b,b+n);
	int p=0,ans=456789;
	for(int i=0;i<n;i++)p+=(a[i]!=b[i]);
	if(p==0)ans=0;
	cin>>m;
	for(int i=1;i<=m;i++){
		int c,d;cin>>c>>d;
		c--;d--;
		if(a[c]!=b[c]&&a[d]==b[c])p--;
		else if(a[c]==b[c]&&a[d]!=b[c])p++;
		if(a[d]!=b[d]&&a[c]==b[d])p--;
		else if(a[d]==b[d]&&a[c]!=b[d])p++;
		swap(a[c],a[d]);
		if(p==0)ans=min(ans,i);
	}
	if(ans>m)cout<<"-1\n";
	else cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 7844
//read by human
// 1 min = 60 sec
// 1 hour = 60 min = 3600 sec

 

#include <iostream>

 

using namespace std;

 

int main()
{
   int i, h, m, s;     
   cin >> i;
   h = i / 3600;
   m = i / 60 - h * 60 ;
   s = i % 60; 
   cout << h << ":" << m << ":" << s << endl;
  
   return 0;
}


Measured memory_bytes: 3088
#include<stdio.h>
#include<string.h>
const int N = 1300;
int main()
{
	char str[N];
	while(fgets(str, 1300, stdin))
	{
		int sum = 0;
		if(str[0] == '0')
		{
			break;
		}
		for(int i = 0; i < strlen(str) - 1; i++)
		{
			sum += str[i] - '0' ; 
		}
		printf("%d\n", sum);
	}
	return 0;
} 


Measured memory_bytes: 2028
#include<stdio.h>
int main(){
   int i,n,w,k;
   int array[1000];
   scanf("%d",&n);
   for(i=0;i<n;i++){
      scanf("%d",&array[i]);
   }
   w=0; k=0;
   for(i=0;i<n;i++){
      if(array[i]%2==0){
         k++;
      }
      if((array[i]%2==0&&array[i]%3==0)||(array[i]%2==0&&array[i]%5==0)){
         w++;
      }
   }
   if(k==w){
      printf("APPROVED\n");
   } else {
      printf("DENIED\n");
   }
   return 0;
}


Measured memory_bytes: 1648
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<n; i++)
#define PI 3.14159265359
#define INF 1000100100
#define all(x) (x).begin(),(x).end()
typedef long long ll;
#define P pair<int, int>
#define PP pair<P,P>
using namespace std;
int n,m,q;
int sim[100];
int dt[100][4];
int ans;

int main(){
    int n,m; cin >> n >> m;
    int f=n/2; int s=f+1;
    bool sumi=false;
    rep(i,m){
        if(s-f>=n/2 && n%2==0 && sumi==false){
            f--;
            sumi=true;
        }
        cout << f << ' ' << s << endl;
        f--; s++;
    }
return 0;
}







Measured memory_bytes: 3592
#include <iostream>
#include <cstdio>
#include <cctype>
#include <cstring>
using namespace std;
int main()
{
    string s, p;
    cin >> s >> p;
    for (int i = 0; i < s.size(); i++)
    {
        string str1, str2, str3;
        str1 = s.substr(0, i);
        str2 = s.substr(i, s.size() - i);
        str3 = str1.insert(0, str2);
        if (str3.find(p) != string::npos)
        {
            cout << "Yes" << endl;
            break;
        }
        else if (i == s.size() - 1)
        {
            cout << "No" << endl;
        }
    }
    
    return 0;
}


Measured memory_bytes: 3188
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,s,n) for (int i = (s); i < (n); ++i)
#define rrep(i,n,g) for (int i = (n)-1; i >= (g); --i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define len(x) (int)(x).size()
#define dup(x,y) (((x)+(y)-1)/(y))
#define pb push_back
#define Field(T) vector<vector<T>>
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main() {
  int m;
  cin >> m;
  cout << 48 - m << endl;
  return 0;
}

Measured memory_bytes: 3644
// I SELL YOU...! 
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
#include<chrono>
#include<iomanip>
#include<map>
#include<set>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using TP = tuple<ll,ll,ll>;
void init_io(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(18);
}
const ll MAX = 310;
const ll INF = 1e15;
signed main(){
  init_io();
  ll n,K;
  cin >> n >> K;
  vector<ll> h(n+1);
  h[0] = 0;
  for(int i=0;i<n;i++){
    cin >> h[i+1];
  }
  vector<vector<ll>> dp(MAX,vector<ll>(MAX,INF));
  dp[0][0] = 0;
  for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
      ll v = INF;
      for(int k=0;k<i;k++){
        v = min(v,dp[k][j-1]+max(0ll,h[i]-h[k]));
      }
      dp[i][j] = v;
    }
  }
  ll ans = INF;
  for(int i=0;i<=n;i++){
    ans = min(ans,dp[i][n-K]);
    /*
    for(int j=0;j<=n;j++){
      cout << dp[i][j] <<" ";
    }
    cout << endl;
    */
  }
  cout << ans<<endl;
}


Measured memory_bytes: 3996