akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections;
using System.Linq;

namespace C
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            string[] In = Console.ReadLine().Split(' ');
            int[] D = new int[n];
            for(int i=0; i < n; i++)
            {
                D[i] = int.Parse(In[i]);
            }
            Array.Sort(D);
            int r_mid = n / 2;
            Console.WriteLine(D[r_mid] - D[r_mid - 1]);
        }
    }
}


Measured memory_bytes: 35072
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<climits>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<bitset>
#include<iomanip>
using namespace std;

#define rep(i,j,n) for(int i=(j);i<(n);i++)
#define rep2(i,j,n) for(int i=(j);i<=(n);i++)
#define all(i) i.begin(),i.end()
#define INF 1e9

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;
typedef pair<int, int> pi;
typedef long long i64;

int main() {
	string s;
	set<string> st{ "a","i","u","e","o" };
	cin >> s;
	if (st.count(s)) cout << "vowel\n";
	else cout << "consonant\n";
}

Measured memory_bytes: 256
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<map>
#include<iomanip>
#include<set>
#include<bitset>
#define rep(index,num) for(int index=0;index<num;index++)
#define rep1(index,num) for(int index=1;index<=num;index++)
#define brep(index,num) for(int index=num-1;index>=0;index--)
#define brep1(index,num) for(int index=num;index>0;index--)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-7
#define mp(a1,a2) make_pair(a1,a2)
#define ALL(a) (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()
typedef long long ll;
typedef long double ld;
using namespace std;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
typedef vector<pll> vpll;
ll INFl=1e+18+1;
int INF=1e+9+1;
int main(){
	string S;
	int K;
	scan(S>>K);
	int N=S.size();
	rep(i,N){
		if(i==N-1){
			S[i]='a'+((S[i]-'a'+K)%26);
		}
		else if(S[i]!='a'){
			int zure=26-(S[i]-'a');
			if(zure<=K){
				S[i]='a';
				K-=zure;
			}
		}
		if(K==0) break;
	}
	prin(S);
	return 0;
}


Measured memory_bytes: 512
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
#include<string>
#include<iostream>
#include<set>
#include<map>
#include<bitset>

using namespace std;
typedef long long ll;
#define i_7 1000000007
#define i_5 1000000005

ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    else return c+i_7;
}
typedef pair<int,int> i_i;
typedef pair<ll,ll> l_l;
#define inf 100000000/*10^8*/



////////////////////////////////////////


int main(){
    string s;cin>>s;
    int len=s.size();
    int ans=0;
    for(int i=0;i<=len-2;i++){
        if(s[i]!=s[i+1])ans++;
    }cout<<ans;
    
    return 0;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define all(x) (x).begin(),(x).end()
#define int long long
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a,b,c;
    cin >> a >> b >> c;
    cout << (a - b + 1) * (a - c + 1) << '\n';
    return 0;
}


Measured memory_bytes: 256
#[allow(unused_imports)]
use std::cmp::{max, min};
use std::io::{stdin, stdout, BufWriter, Write};

#[derive(Default)]
struct Scanner {
    buffer: Vec<String>,
}

impl Scanner {
    fn next<T: std::str::FromStr>(&mut self) -> T {
        loop {
            if let Some(token) = self.buffer.pop() {
                return token.parse().ok().expect("Failed parse");
            }
            let mut input = String::new();
            stdin().read_line(&mut input).expect("Failed read");
            self.buffer = input.split_whitespace().rev().map(String::from).collect();
        }
    }
}

fn main() {
    let mut scan = Scanner::default();
    let out = &mut BufWriter::new(stdout());
    let n = scan.next();
    let m = scan.next();
    let mut a = vec![vec![0; m]; n];
    let mut v = vec![0; m];

    for i in 0..n {
        for j in 0..m {
            a[i][j] = scan.next();
        }
    }
    for i in 0..m {
        v[i] = scan.next();
    }

    for i in 0..n {
        let mut ret = 0;
        for j in 0..m {
            ret += a[i][j] * v[j];
        }
        writeln!(out, "{}", ret).ok();
    }
}



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

const long long MOD = 1000000007;

long long Sum (long long LL, long long RR) {
	return (LL+RR)*(RR-LL+1)/2;
}

int main () {
	long long N, K;
	cin >> N >> K;
	long long ans = 0;
	for (long long i = K; i <= N+1; ++i) {
		ans += (Sum (N-i+1, N) - Sum (0, i-1) + 1);
		ans %= MOD;
	}
	cout << ans << endl;
	return 0; 
}	 

Measured memory_bytes: 3636
n = int(input())
a = [int(i) for i in input().split()]
#import numpy as np
#n = 100
#a = np.random.randint(1, 100, n)
a = sorted(a)
minsum = float('inf')
for i in range(a[0], a[-1]+1):
  cnt = 0
  for ai in a:
    cnt += (ai - i)**2
  if cnt <= minsum:
    minsum = cnt
print(minsum)

Measured memory_bytes: 9192
# https://atcoder.jp/contests/abc091/tasks/abc091_b
from collections import defaultdict
n = int(input())
s = defaultdict(int)
for _ in range(n):
    s[input()] += 1

m = int(input())
t = defaultdict(int)
for _ in range(m):
    t[input()] += 1


ans = 0
for k, v in s.items():
    if k in t:
        v -= t[k]
    ans = max(ans, v)
print(ans)

Measured memory_bytes: 38256
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;

int comp_id = 0;
vector<int> edges[100001];

int comp[100001];

void bfs(int from) {
    queue<int> q;
    q.push(from);
    comp[from] = comp_id;

    while (!q.empty()) {
        int current = q.front();
        q.pop();

        for (int to : edges[current]) {
            if (comp[to] == -1) {
                comp[to] = comp_id;
                q.push(to);
            }
        }
    }
}

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

    int N, M;
    cin >> N >> M;

    vector<int> P;
    P.resize(N);

    int pos[100001];

    for (int i=0; i<N; i++) {
        cin >> P[i];
        pos[P[i]] = i;
    }

    for (int i=0; i<M; i++) {
        int f, t;
        cin >> f >> t;

        edges[f].push_back(t);
        edges[t].push_back(f);
    }

    memset(comp, -1, sizeof(comp));

    for (int i=1; i <= N; i++) {
        if (comp[i] == -1) {
            comp_id++;
            bfs(i);
        }
    }


    int result = 0;
    for (int i=0; i<N; i++) {
        int value = P[i];
        int actual_pos = pos[P[i]];
        int value_there = i + 1;

        if (comp[value] == comp[value_there]) {
            result++;
        }
    }

    cout << result << endl;
    return 0;
}

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

#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
using namespace std;
using ll = long long;

int main() {
    FAST;

    int n, i, j, ans = 0;
    cin >> n;
    string s;
    cin >> s;

    i = 0;
    j = n-1;

    while (i < j) {
        if (s[i] == 'R') {
            ++i;
            continue;
        }
        if (s[j] == 'W') {
            --j;
            continue;
        }
        if (s[i] != s[j]) {
            ++i;
            --j;
            ++ans;
        }
    }

    cout << ans;

    return 0;
}


Measured memory_bytes: 3768
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please

const int cm = 1 << 17;
char cn[cm], * ci = cn + cm, ct;
inline char getcha() {
	if (ci - cn == cm) { fread_unlocked(cn, 1, cm, stdin); ci = cn; }
	return *ci++;
}
inline int getint() {
	int A = 0;
	if (ci - cn + 16 > cm) while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';
	else while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';
	return A;
}

const int dm = 1 << 20;
char dn[dm], *di = dn, dt;
inline void putint(int X) {
	if (X == 0) {
		*di++ = '0';
		*di++ = ' ';
		return;
	}
	int keta = 0;
	char C[10];
	while (X) {
		*(C + keta) = '0' + X % 10;
		X /= 10;
		keta++;
	}
	for (int i = keta - 1; i >= 0; i--) *di++ = (*(C + i));
	*di++ = ' ';
}

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


	int N = getint();
	int A[100000];
	ll ans = (A[0] = getint());

	rep1(i, N - 1) {
		A[i] = getint();
		if (i & 1) ans = ans - A[i];
		else ans = ans + A[i];
	}

	putint(ans);
	rep(i, N - 1) {
		putint((ans = 2 * A[i] - ans));
	}

	fwrite_unlocked(dn, di - dn, 1, stdout);

	Would you please return 0;
}

Measured memory_bytes: 2816
#include<iostream> 
using namespace std;
static const int N = 105;

int Bubble_Sort(int a[],int n)  //冒泡排序 升序 
{
	int count=0,temp;
	for(int i=1;i<n;i++)
	for(int j=0;j<n-i;j++)
	{
		if(a[j]>a[j+1])
		{
			count++;
			temp = a[j];
			a[j] = a[j+1];
			a[j+1]= temp;
		 } 
	}
	return count;
}

int main()
{
	int n,count;
	int a[N];
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	count=Bubble_Sort(a,n);
	for(int i=0;i<n;i++)
	{
		if(i<n-1)
		cout<<a[i]<<' ';
		else
		cout<<a[i]<<endl;
	}
	cout<<count<<endl;
}


Measured memory_bytes: 3124
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <string>
#include <cstdlib>
using namespace std;
const double pi =  3.1415926;
int get(int x) {
    return (2000-(x+1))/200+1;
}
int main() {

    int a, b, c, k;
    while (scanf("%d %d %d",&a,&b,&c)!=EOF) {
        scanf("%d",&k);
        while (k--) {
            if (a>=b) {
                b*=2;
            }
            else {
                c*=2;
            }
        }
        printf("%s\n",a<b&&b<c?"Yes":"No");
    }
    return 0;
}


Measured memory_bytes: 3168
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(t) (t).begin(),(t).end()
typedef long long ll;

int main() {
	string Ans="No";
	int N; cin >> N;
	vector<int> first(N);
	vector<int> second(N);
	REP(i,N){
		cin >> first[i];
		cin >> second[i];
		if (i>=2){
			if( (first[i]==second[i]) && (first[i-1]==second[i-1]) && (first[i-2]==second[i-2]) ){
				Ans="Yes";
			}
		}
	}
	cout << Ans << '\n';
	return 0;
}


Measured memory_bytes: 3600
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <iomanip>
#include <fstream>
#include <unordered_map>
#include <unordered_set>
#include <assert.h>
using namespace std;


#define REP(i, n) for(ll i = 0;i < n;i++)
#define REPR(i, n) for(ll i = n;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
#define FORR(i, m, n) for(ll i = m;i >= n;i--)
#define REPO(i, n) for(ll i = 1;i <= n;i++)
#define ll long long
#define INF (ll)1 << 60
#define MINF (-1 * INF)
#define ALL(n) n.begin(),n.end()
#define MOD 1000000007
#define P pair<ll, ll>



int main() {
	ll a, b, c;
	cin >> a >> b >> c;
	cout << c << " " << a << " " << b << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		try (Scanner scanner = new Scanner(System.in)) {
			String line = scanner.nextLine();
			if (line.indexOf('a') >= 0 && line.indexOf('b') >= 0 && line.indexOf('c') >= 0) {
				System.out.println("Yes");
			} else {
				System.out.println("No");
			}
		}
	}
}


Measured memory_bytes: 21844
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>

using namespace std;

int main(){

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

  vector<long long> dp(n,10000000007);

  dp[0]=a[0];

  for(int i=1;i<n;i++){
    if(a[i]>=dp[i-1])dp[i]=a[i];
    else{
      dp[upper_bound(dp.begin(),dp.end(),a[i])-dp.begin()]=a[i];
    }
  }

  for(int i=n-1;i>=0;i--){
    if(dp[i]!=10000000007){
      cout << i+1 << endl;
      break;
    }
  }

}

Measured memory_bytes: 1792
import java.util.*;

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

		Scanner sc = new Scanner(System.in);
		
		String s = sc.next();
		String t = sc.next();
		boolean flag = false;
		for(int n=0;n<s.length();n++){
			String st = "";
			for(int m=0;m<s.length();m++){
				st += s.charAt((m+n)%s.length());
			}
			if(st.equals(t)){
				flag = true;
				break;
			}
		}
		if(flag) System.out.println("Yes");
		else System.out.println("No");
	}
}

Measured memory_bytes: 26708
N = int(input())
H = list(map(int,input().split()))

cnt = [0]
for i in range(N-1):
    if H[i] >= H[i+1]:
        continue
    else:
        cnt.append(i+1)
cnt.append(N)

ans = []
for i in range(len(cnt)-1):
    ans.append(cnt[i+1]-cnt[i]-1)
print(max(ans))

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

int main() {
  int a, b, k;
  cin >> a >> b >> k;
  rep(i, b-a+1){
    if(i < k || i > b-a-k) cout << a + i << endl;
  }
  return 0;
}

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

using namespace std; 
int main(){
  string s;  
  while(cin>>s&&s!="#"){  
int n=s.size();
    int a[50];    
    for(int i=0;i<n;i++){
      if(s[i]=='y'||s[i]=='u'||s[i]=='i'||s[i]=='o'||s[i]=='p'||s[i]=='h'||s[i]=='j'||s[i]=='k'||s[i]=='l'||s[i]=='n'||s[i]=='m'){
	a[i]=0;
      }else{
	a[i]=1;
      }
    }
  
    int ans=0;
    for(int i=0;i<n-1;i++){
      if(a[i]==a[i+1]){
	continue;
      }else ans++;
    }
    cout<<ans<<endl;
  }
  return 0;
 
}

Measured memory_bytes: 3096
#include <bits/stdc++.h>
using  namespace std;
typedef long long ll;
#define RAP(i, n) for(ll i=0;i<(n);i++)
#define FOR(i, a, b) for(ll i=(a);i<(b);i++)

int main(){
  ll n, m, ans = 0;
  cin >> n >> m;
  if(n>1){
   ans += n * (n-1) / 2;
  }
  if(m>1){
    ans += m * (m-1) / 2;
  }
  
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
typedef int ll;
typedef pair<ll,ll> P;
typedef double db;
struct T{
	ll first,second,third;
	bool operator<(const T& t)const{
		return first!=t.first?(first<t.first):(second!=t.second?second<t.second:third<t.third);
	}
};
ll w,h,g[10][10];
ll cx,cy;
inline vector<P> doko(ll y,ll x){
	vector<P> v;
	for(ll nx=x+1;nx<w;nx++){
		if(g[y][nx]>0) v.push_back(P(y,nx));
		if(g[y][nx]==1) break;
	}
	for(ll nx=x-1;nx>=0;nx--){
		if(g[y][nx]>0) v.push_back(P(y,nx));
		if(g[y][nx]==1) break;
	}
	for(ll ny=y+1;ny<h;ny++){
		if(g[ny][x]>0) v.push_back(P(ny,x));
		if(g[ny][x]==1) break;
	}
	for(ll ny=y-1;ny>=0;--ny){
		if(g[ny][x]>0) v.push_back(P(ny,x));
		if(g[ny][x]==1) break;
	}
	return v;
}
ll n;
ll id[10][10];
set<T> t;
ll dfs(ll y,ll x,ll s){
	if(t.count((T){y,x,s})) return 0;
	ll res=0;
	vector<P> v=doko(y,x);
	if(s==(1<<n)-1){
		for(ll i=0;i<v.size();i++){
			if(g[v[i].first][v[i].second]==2) return 1;
		}
		t.insert((T){y,x,s});
		return 0;
	}
	if(s) g[y][x]=-1;
	for(ll i=0;i<v.size();i++){
		if(g[v[i].first][v[i].second]==2) continue;
		res+=dfs(v[i].first,v[i].second,s|(1<<id[v[i].first][v[i].second]));
	}
	g[y][x]=1;
	if(res==0) t.insert((T){y,x,s});
	return res;
}

int main()
{while(1){
	scanf("%d%d",&w,&h);
	n=0;
	t.clear();
	memset(id,-1,sizeof(id));
	if(!w) return 0;
	for(ll i=0;i<h;i++) for(ll j=0;j<w;j++){
		scanf("%d",&g[i][j]);
		if(g[i][j]==2){
			cx=j,cy=i;
		}
		else if(g[i][j]){
			id[i][j]=n;
			n++;
		}
	}
	printf("%d\n",dfs(cy,cx,0));
}}

Measured memory_bytes: 49508
#include <iostream>
#include <vector>
#include <bitset>
#include <utility>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
 
using namespace std;
typedef long long ll;
 
int main(){
  int N;
  cin >> N;
  ll ans=0;
  for(int i=1;i<=N;i++){
    if(((i%3)!=0) & ((i%5)!=0)){
      ans+=i;
    }
  }

  cout << ans << endl;
  
  return 0;
}


Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,c,k;
    scanf("%d%d%d",&a,&b,&c);
    scanf("%d",&k);
    int ans=a+b+c;
    int t=max(a,b);
    t=max(t,c);
    ans-=t;
    for(int i=0;i<k;i++)
    {
        t*=2;
    }
    ans+=t;
    printf("%d\n",ans);
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define lli long long int
#define MOD 1000000007
#define INF INT_MAX // 2147483647
#define INFLL LLONG_MAX // 9223372036854775807
#define rep(i, n) for(int i=0; i<(int)(n); i++)
#define all(v) v.begin(), v.end()
#define endl "\n"
#define vi vector<int>
#define vvi vector<vector<int>>
#define Yes() cout << "Yes" << endl
#define YES() cout << "YES" << endl
#define No() cout << "No" << endl
#define NO() cout << "NO" << endl
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(10);
    lli h, n, sum = 0;
    cin >> h >> n;
    rep(i, n){
        lli in;
        cin >> in;
        sum += in;
    }
    if(sum >= h) Yes();
    else No();
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
#define INF (1 << 30)
 
struct edge{
 
  int cost, to;
 
};
 
struct state{
 
  int node, cost;
  bool operator <(const state &b)const{
    return cost > b.cost;
  }
};
 
int n;
int d[10001];
vector<edge> glaph[10001];
priority_queue<state> qu;
 
void sss(){
 
  fill(d,d+10001,INF);
  qu.push((state){0,0});
  d[0] = 0;
 
  while(!qu.empty()){
 
    state info;
    info = qu.top();
    qu.pop();
 
    for(int i = 0; i < (double)glaph[info.node].size(); i++){
      if(d[glaph[info.node][i].to] > glaph[info.node][i].cost + d[info.node]){
      d[glaph[info.node][i].to] = glaph[info.node][i].cost + d[info.node];
      qu.push((state){glaph[info.node][i].to,d[info.node]}); 
      }
    }
  }
 
  for(int i = 0; i < n; i++){
    cout << i << " " << d[i] << endl;
  }
   
 
 
 
}
 
int main(){
 
  cin >> n;
 
  for(int i = 0; i < n; i++){
    int k, v, c, u;
    cin >> u >> k;
    for(int j = 0; j < k; j++){
      cin >> v >> c;
      glaph[u].push_back((edge){c,v});
    }
  }
 
  sss();
 
 
}

Measured memory_bytes: 1552
const main = arg => {
    const input = arg.trim().split("\n");
    const n = parseInt(input[0]);
    const arr = input[1].split(" ").map(item => BigInt(item));

    if(arr.includes(0n)){
        console.log(0)
        return
    } 
    let ret = 1n
    for(let item of arr){
        ret = ret*item
        if(ret > BigInt(1000000000000000000)){
            console.log('-1')
            return
        }
    }
    console.log(ret.toString())
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));  


Measured memory_bytes: 43920
/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <iostream>

using namespace std;

int main()
{
 int N ;
 cin>> N ; 
 cout<<N*N*N;
 
 
 

    return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
///////////////////////////////////////////
const long long int INF = 1LL<<60;
const long long int Mod = 1000000007;
using ll = long long int; using ci = const int;
using vi = vector<int>;  using Vi = vector<long long int>;
using P = pair<int, int>;  using PLL = pair<ll, ll>;
using matrix = vector<vector<ll>>;
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define rep(i,N) for(ll i = 0; i < (ll)N; i++)
#define repi(i,a,b) for(ll i = ll(a); i < ll(b); ++i)
template<class T>bool chmax(T &former, const T &b) { if (former<b) { former=b; return true; } return false; }
template<class T>bool chmin(T &former, const T &b) { if (b<former) { former=b; return true; } return false; }
template<class T>T sqar(T x){ return x*x; }//sqrt(x)は平方根;
#define Sort(v) std::sort(v.begin(), v.end(), std::greater<decltype(v[0])>()) //降順でVをソート
#define p_queue(v) priority_queue<v, vector<v>, greater<v> >
template<class T> inline void princ(T x){cout<<x<<" ";}; 
template<class T> inline void print(T x){cout<<x<<"\n";};
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
///////////////////////////////////////////////////////////////////////////////////

ll n,m,p,v;
Vi a;

bool ck(ll id){
	ll v2 = v*m;
	v2 -= m*p;//idの問題と上からp-1問の問題.
	v2 -= id*m;//idより小さい問題.
	if(v2<0){
		if(a[a.size()-p]<=a[id]+m)return true;
		else return false;
	}else{
		ll now = a[id]+m;
		if(now<a[a.size()-p])return false;
		repi(j,id+1,a.size()-p+1){
			if(now-a[j]<0){
				break;
			}
			v2 -= now-a[j];
			if(v2<=0){
				break;
			}
		}
		if(v2<=0)return true;
		else return false;
	}
}

int main(){
	cin.tie(0);ios::sync_with_stdio(false);
	std::cout<<std::fixed<<std::setprecision(30);
	cin>>n>>m>>v>>p;
	a.resize(n);
	rep(i,n){
		cin>>a[i];
	}
	sort(all(a));
	ll mid, ok = a.size()-1, ng = -1;
	while(abs(ok-ng)>1){
		mid = (ok+ng)/2;
		if(ck(mid))ok = mid;
		else ng = mid;
	}//midではなくokを使わないとバグる!
	//ck(0);
	print(a.size()-ok);
	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  long long N,x,y,sum;
  long long min,max;
  
  while(1){
    cin >> y >> x;
    if(x == 0 && y == 0)break;
    for (int i = 0; i < y; i++) {
          for (int j = 0; j < x; j++) {
            if(j == 0 || j == x-1 || i == 0 || i == y-1)cout << "#";
            else cout << ".";
    	  } 
  	  cout << endl;
    } 
      	  cout << endl;
  }
}


Measured memory_bytes: 3088
#include <bits/stdc++.h>
#define rep(i, z, n) for(int i = z; i < n; i++)
#define all(v) v.begin(), v.end()
typedef long long ll;
#define PI 3.14159265358979

//const int64_t INF = 1LL << 60;
const int INF = 1 << 29;
//const int64_t MOD = 1000000007;
//const int64_t INF = 998244353;
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 namespace std;
//#define P pair<int, int>
typedef pair<int, int> P;

int main(){
    int N;
    cin >> N;
    vector<double> x(N), y(N);
    vector<pair<double, double>> p(N);
    rep(i, 0, N){
        cin >> x.at(i) >> y.at(i);
        p.at(i) = make_pair(x.at(i), y.at(i));
    }
    sort(all(p));
    double sum = 0;
    do{
        rep(i, 0, N - 1){
            double a = p.at(i + 1).first;
            double b = p.at(i + 1).second;
            double c = p.at(i).first;
            double d = p.at(i).second;
            sum += pow(pow(a - c, 2) + pow(b - d, 2), 0.5);
        }
    }while(next_permutation(all(p)));
    rep(i, 1, N + 1){
        sum /= (double)i;
    }
    cout << fixed << setprecision(10) << sum << endl;
}

Measured memory_bytes: 640
#include<stdio.h>
int main(void)
{
  int n;
  int a,b,c;
  int wa;
  do{
  scanf("%d",&n);
  }while(n<0||1000000000<n);
  a=n/500;
  b=n%500;
  c=b/5;
  
  wa=a*1000+c*5;
  
  printf("%d",wa);
  return 0;
}

Measured memory_bytes: 1736
#include <stdio.h>
#include <iostream>
#include <string>
using namespace std;
int main(void){
  
  int N,K;
  cin >> N >> K;
  int t=K,i;
  for(i=1;i<N;i++){
    t *= K-1;
  }
  cout << t << endl;
return 0;
} 

Measured memory_bytes: 256
using System;
using System.Linq;

namespace ConsoleApp
{
    class Program
    {
        static void Main(string[] args)
        {
            var input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            Console.WriteLine(input[0] * 500 >= input[1] ? "Yes" : "No");
        }
    }
}

Measured memory_bytes: 13268
#include <cstdio>
#include <cctype>
#include <utility>
#include <string>
using namespace std;

#define _gp(l) const auto gcu{getchar##l}; const auto pcu{putchar##l}
#ifdef __linux
_gp(_unlocked);
#else
_gp();
#endif
#define _DEF(r, n, ...) inline r n(__VA_ARGS__) noexcept
#define _T template <typename T>
#define _HT template <typename H,typename... T>
_T _DEF(T,in,int c){T n=0;int m=1;while(isspace(c)){c=gcu();}if(c=='-')m=-1,c=gcu();
	do{n=10*n+(c-'0'),c=gcu();}while(c>='0'&&c<='9');return m*n;}
_DEF(int,in,){return in<int>(gcu());}
#define _SCAN(...) _DEF(bool,scan,__VA_ARGS__)
_T _SCAN(T &n){int c=gcu();return c==EOF?false:(n=in<T>(c),true);}
_DEF(bool, scan, int &c){c=gcu();gcu();return c!=EOF;}
#ifdef _GLIBCXX_STRING
_SCAN(string &s){int c;s="";
	for(;;){c=gcu();if(c=='\n'||c==' ')return true;else if(c==EOF)return false;s+=(char)c;}}
#endif
_HT _SCAN(H &h,T&&... t){return scan(h)&&scan(t...);}
#define _OUT(...) _DEF(void,out,__VA_ARGS__)
#define _OUTL(...) _DEF(void,outl,__VA_ARGS__)
_OUT(bool b){pcu('0'+b);} _OUT(const char *s){while(*s)pcu(*s++);} _OUT(char c){pcu(c);}
#ifdef _GLIBCXX_STRING
_OUT(string s){for(char c:s)pcu(c);}
#endif
_T _OUT(T n){static char b[20];char *p=b;T m=n<0?pcu('-'),-1:1;
	if(!n)*p++='0';else while(n)*p++=(char)(n%10*m+'0'),n/=10;while(p!=b)pcu(*--p);}
_OUTL(){out('\n');}
#ifdef _GLIBCXX_VECTOR
_T _OUT(vector<T> v){for(T &x:v)out(&x == &v[0]?"":" "),out(x);}
#endif
_HT _OUT(H&& h, T&&... t){out(h);out(move(t)...);}
template <typename... T> _OUTL(T&&... t){out(move(t)...);outl();}
struct range{
	int e,b=0,s=1; range(int _b,int _e,int _s):e(_e),b(_b),s(_s){} range(int _b,int _e): e(_e), b(_b){} range(int _e):e(_e){}
	struct it { int v, s; it (int _v, int _s) : v(_v), s(_s) {} operator int()const{return v;} operator int&(){return v;} int operator*()const{return v;}
		it& operator++(){v+=s;return *this;} }; it begin() {return {b, s};} it end() {return {e, s};}};

int main() {
	string s;
	int a {};
	for (int n {in()}; n; n--) {
		scan(s);
		if((a += s[0] == 'A' ? 1 : -1) < 0) {
			outl("NO");
			return 0;
		}
	}
	outl(a ? "NO" : "YES");
}


Measured memory_bytes: 2688
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
const ll MOD = 1000000007;

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

    int H, W, K;
    cin >> H >> W >> K;

    auto f = [](int n) {
        bool f = false;
        while (n) {
            if (n % 2) {
                if (f) return true;
                f = true;
            }
            else f = false;
            n /= 2;
        }
        return false;
    };

    vector<int> v(W-1);
    int N = 0;
    for (int bit = 0; bit < 1<<W-1; bit++) {
        int n = bit;
        if (f(n)) continue;
        for (int i = 0; i < W-1; i++) {
            if (n % 2) v[i]++;
            n /= 2;
        }
        N++;
    }

    vector<vector<ll>> dp(H+1, vector<ll>(W));
    dp[0][0] = 1;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            int x = 0;
            if (j > 0) {
                dp[i+1][j-1] += dp[i][j] * v[j-1] % MOD;
                dp[i+1][j-1] %= MOD;
                x += v[j-1];
            }
            if (j < W-1) {
                dp[i+1][j+1] += dp[i][j] * v[j] % MOD;
                dp[i+1][j+1] %= MOD;
                x += v[j];
            }
            dp[i+1][j] += dp[i][j] * (N - x) % MOD;
            dp[i+1][j] %= MOD;
        }
    }
    cout << dp[H][K-1] << "\n";
}

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

int main() {
  int N,W;
  cin >> N >> W;
  vector<pair<int,int>> wv(N);
  for (int i=0; i<N; i++) {
    cin >> wv[i].first >> wv[i].second;
  }
  long smallw = wv[0].first;
  //cerr << smallw << endl;
  
  sort(wv.begin(),wv.end());
  
  /*for (int i=0; i<N; i++) {
    cerr << wv[i].first << " " << wv[i].second << endl;
  }*/
  
  int cc0 = 0;
  int cc1 = 0;
  int cc2 = 0;
  int cc3 = 0;
  for (int i=0; i<N; i++) {
    if (wv[i].first == smallw) {
      cc0++;
      continue;
    }
    if (wv[i].first == smallw+1) {
      cc1++;
      continue;
    }
    if (wv[i].first == smallw+2) {
      cc2++;
      continue;
    }
    cc3++;
  }
  
  vector<long> vv0(cc0+1,0);
  vector<long> vv1(cc1+1,0);
  vector<long> vv2(cc2+1,0);
  vector<long> vv3(cc3+1,0);
  for (int i=cc0-1; i>=0; i--) {
    vv0[cc0-i] = vv0[cc0-1-i] + wv[i].second;
    cerr << vv0[cc0-i] << ' ';
  }
  cerr << endl;
  for (int i=cc1-1; i>=0; i--) {
    vv1[cc1-i] = vv1[cc1-1-i] + wv[i+cc0].second;
    cerr << vv1[cc1-i] << ' ';
  }
  cerr << endl;
  for (int i=cc2-1; i>=0; i--) {
    vv2[cc2-i] = vv2[cc2-1-i] + wv[i+cc0+cc1].second;
    cerr << vv2[cc2-i] << ' ';
  }
  cerr << endl;
  for (int i=cc3-1; i>=0; i--) {
    vv3[cc3-i] = vv3[cc3-1-i] + wv[i+cc0+cc1+cc2].second;
    cerr << vv3[cc3-i] << ' ';
  }
  cerr << endl;
  long ans = 0;
  long term = 0;
  for(int i=0; i<cc0+1; i++) {
    for(int j=0; j<cc1+1; j++) {
      for(int k=0; k<cc2+1; k++) {
        for(int l=0; l<cc3+1; l++) {
          if ((i+j+k+l)*smallw+j+k*2+l*3 > W) {
            continue;
          }
          term = vv0[i] + vv1[j] + vv2[k] + vv3[l];
          ans = max(term,ans);
          term = 0;
        }
      }
    }
  }
  cout << ans << endl;
}

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

const int _ = 3e6 + 7 , MOD = 998244353;
int jc[_] , inv[_] , N , M;

int poww(long long a , int b){
	int times = 1;
	while(b){if(b & 1) times = times * a % MOD; a = a * a % MOD; b >>= 1;}
	return times;
}

void init(int mx){
	jc[0] = 1; for(int i = 1 ; i <= mx ; ++i) jc[i] = 1ll * jc[i - 1] * i % MOD;
	inv[mx] = poww(jc[mx] , MOD - 2);
	for(int i = mx - 1 ; i >= 0 ; --i) inv[i] = inv[i + 1] * (i + 1ll) % MOD;
}

int binom(int p , int q){return p < q ? 0 : 1ll * jc[p] * inv[q] % MOD * inv[p - q] % MOD;}

int main(){
	cin >> N >> M; init(3 * M + N); int sum = 0;
	for(int i = 0 ; i <= N && i <= M ; ++i){
		if((3 * M - i) & 1) continue;
		sum = (sum + 1ll * binom(N , i) * binom((3 * M - i) / 2 + N - 1 , N - 1)) % MOD;
	}
	cout << (sum - 1ll * N * binom(M - 1 + N - 1 , N - 1) % MOD + MOD) % MOD; return 0;
}


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

int main() {
  int n;
  cin >> n;
  long long la = 2, lb = 1, lc = 3;
  if(n == 1){
    cout << 1 << endl;
  }else{
    for(int i = 2; i < n; i++){
      swap(la,lb);
      swap(lb,lc);
      lc = la + lb;
    }
    cout << lc << endl;
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> l_l;
typedef pair<int , int> i_i;
typedef vector<ll> vl;
typedef vector<int> vi;
typedef vector<char> vec;
typedef vector<bool> veb;
typedef vector<string> ves;
typedef vector<vector<ll>> vvl;
typedef vector<vector<int>> vvi;
typedef vector<vector<char>> vvec;
typedef vector<vector<bool>> vveb;
typedef vector<vector<string>> vves;
#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 rep2(i,n) for(int i=2;i<(int)(n);i++)
#define repk(i,k,n) for(int i=k;i<(int)(n);i++)
#define fs first
#define sc second
#define pb push_back
#define pp pop_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define maxel(a) *max_element(all(a))
#define minel(a) *min_element(all(a))
#define acc accumulate
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define mod (1000000007)
typedef long long int64;
//const int64 INF = 1LL << 58;
#define dame { puts("-1"); return 0;}
#define YES { cout << "YES" << endl; return 0; }
#define NO { cout << "NO" << endl; return 0; }
#define Yes { cout << "Yes" << endl; return 0; }
#define No { cout << "No" << endl; return 0; }
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};

int DigitSum(int n){
	int sum = 0;
	string s = to_string(n);
	while(!s.empty()){
		sum += s.back()-'0';
		s.pp();
	}
	return sum;
}

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

	int n;
	cin >> n;
	int s = DigitSum(n);
	if(n%s==0) Yes
	No

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N,M,a;
  cin>>N>>M;
  string A[N],B[M];
  for(int i=0;i<N;i++) cin>>A[i];
  for(int i=0;i<M;i++) cin>>B[i];
  for(int i=0;i<=N-M;i++){
    for(int j=0;j<=N-M;j++){
      a=1;
      for(int k=0;k<M;k++){
        for(int l=0;l<M;l++){
          if(B[k][l]!=A[i+k][j+l]){
            a=0;
            break;
          }
        }
        if(!a) break;
      }
      if(a) break;
    }
    if(a) break;
  }
  cout<<(a?"Yes":"No")<<endl;
}

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

int main(){
    int H, W;
    cin >> H >> W;
    int S[100][100];
    for(int i=0; i<H; i++){
        string s;
        cin >> s;
        for(int j=0; j<W; j++) S[i][j] = (s[j] == '#' ? -1 : s[j]-'0');
    }

    auto inside = [&](int i, int j){ return i>=0 && i<H && j>=0 && j<W && S[i][j] != -1; };
    int dx[] = {-1, 1, 0, 0};
    int dy[] = {0, 0, -1, 1};
    auto bottom = [](int i, int j){
        if(i%4 == 0){
            vector<int> v = {6, 3, 1, 4};
            return v[j%4];
        }
        if(i%4 == 2){
            vector<int> v = {1, 3, 6, 4};
            return v[j%4];
        }
        if(j%4 == 0){
            vector<int> v = {6, 2, 1, 5};
            return v[i%4];
        }
        if(j%4 == 2){
            vector<int> v = {1, 2, 6, 5};
            return v[i%4];
        }
        exit(-1);
    };

    bool exist[100][100] = {0};
    exist[0][0] = 1;
    queue<vector<int>> que;
    que.push({0, 0});
    while(que.size()){
        auto v = que.front(); que.pop();
        int i = v[0], j = v[1];
        for(int k=0; k<4; k++){
            int x = i+dx[k], y = j+dy[k];
            if(!inside(x, y)) continue;
            if(exist[x][y]) continue;
            if(S[x][y] == bottom(x, y)){
                exist[x][y] = 1;
                que.push({x, y});
            }
        }
    }
    cout << (exist[H-1][W-1] ? "YES" : "NO") << endl;
    return 0;
}



Measured memory_bytes: 3244
#include <bits/stdc++.h>
#define int long long
#define uint unsigned int
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPR(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define FORR(i, a, b) for (int i = (a); i >= (b); --i)
#define ALL(a) (a).begin(), (a).end()
#define ALLR(a) (a).rbegin(), (a).rend()
#define SZ(a) ((int)(a).size())
#define PB(a) push_back(a)
#define EMP emplace
#define EMPB(...) emplace_back(__VA_ARGS__)
#define MP(a, b) make_pair(a, b)
#define MT(...) make_tuple(__VA_ARGS__)
#define Bit(n) (1LL << (n))
using namespace std;
using pii = pair<int, int>;
template <class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template <class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
const int MOD = 1000000007;
const int INF = 1LL << 30;
const double EPS = 1e-10;

int N, A, B;
int a[40], b[40], c[40];
int dp[41][410][410];

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  cin >> N >> A >> B;
  REP(i, N) {
    cin >> a[i] >> b[i] >> c[i];
  }
  fill_n((int*)dp, 41*410*410, INF);
  dp[0][0][0] = 0;
  REP(i, N) REP(j, 410) REP(k, 410) {
    if (j+a[i] < 410 && k+b[i] < 400) chmin(dp[i+1][j+a[i]][k+b[i]], dp[i][j][k]+c[i]);
    chmin(dp[i+1][j][k], dp[i][j][k]);
  }
  int ans = INF;
  for (int i = 1; i*A < 410 && i*B < 410; i++) {
    chmin(ans, dp[N][i*A][i*B]);
  }
  cout << (ans == INF ? -1 : ans) << endl;

  return 0;
}

Measured memory_bytes: 54144
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdlib>
using namespace std;

int main(){
	int n;
	cin >> n;
	for (int i = 0; i < 26; ++i) {
		for (int j = 0; j < 15; ++j) {
			if (4 * i + 7 * j == n) {
				cout << "Yes" << endl;
				return 0;
			}
		}
	}
	cout << "No" << endl;
}

Measured memory_bytes: 256
import java.util.*;
  
public class Main {
    Scanner sc = new Scanner(System.in);
  
    public static void main(String[] args) {
        new Main(); 
    }
  
    public Main() {
        new aoj2585().doIt();
    }
    class aoj2585{
    	int W,H;
    	int map[][] = new int[21][21];
    	int mx[] = {0,1,0,-1};
    	int my[] = {1,0,-1,0};
    	int result = 11;
    	class Par{
    		int y,x;
    		public Par(int y,int x){
    			this.y = y;
    			this.x = x;
    		}
    	}
    	void dfs(int W,int H,Par end,Par start,int cnt){
//    		System.out.println(start.x+" "+start.y+" "+end.x+" "+end.y+" "+cnt);
    		if(cnt < result){
    			for(int i = 0;i < 4;i++){
    				if(start.x + mx[i] < 0 || start.x + mx[i] >= W
    						|| start.y + my[i] < 0 || start.y + my[i] >= H)continue;
    				else if(map[start.y + my[i]][start.x + mx[i]] == 1)continue;
    				else if(map[start.y + my[i]][start.x + mx[i]] == 3){
    					result = Math.min(result,cnt+1);
    				}
    				else{
    					int num = 1;
    					boolean last = false;
    					while(true){
    						num++;
    						if(start.x + mx[i]*num < 0 || start.x + mx[i]*num >= W
    	    						|| start.y + my[i]*num < 0 || start.y + my[i]*num >= H){
    							last = true;
    							break;
    						}
    	    				else if(map[start.y + my[i]*num][start.x + mx[i]*num] == 1)break;
    	    				else if(map[start.y + my[i]*num][start.x + mx[i]*num] == 3){
    	    					result = Math.min(result,cnt+1);
    	    				}
    					}
    					if(!last){
							map[start.y + my[i]*num][start.x + mx[i]*num] = 0;
							dfs(W,H,end,new Par(start.y + my[i]*(num-1),start.x + mx[i]*(num-1)),cnt+1);
							map[start.y + my[i]*num][start.x + mx[i]*num] = 1;
						}
    				}
    			}
    		}
    	}
    	void doIt(){
    		while(true){
    			Par end = null,start = null;
    			W = sc.nextInt();
    			H = sc.nextInt();
    			if(W + H == 0)break;
    			for(int i = 0;i < H;i++){
    				for(int j = 0;j < W;j++){
    					map[i][j] = sc.nextInt();
    					if(map[i][j] == 2){
    						start = new Par(i,j);
    					}
    					else if(map[i][j] == 3)end = new Par(i,j);
    				}
    			}
    			dfs(W,H,end,start,0);
    			if(result == 11)System.out.println("-1");
    			else System.out.println(result);
    			result = 11;
    		}
    	}
    }
}

Measured memory_bytes: 58200
#include <iostream>
#include <algorithm>
#include <utility>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <math.h>
#include <string.h>
#include <iomanip>
#include <numeric>

using namespace std;

using ll = long long;
using pll = pair<ll, ll>;
using vl = vector<ll>;
using vll = vector<vl>;
using vpll = vector<pll>;

#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 pb push_back
#define eb emplace_back

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

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

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

template <class T>
T gcd(T a, T b){
    if( b==0 ) return a;
    else return gcd(b, a%b);
}

template <class T>
T lcm(T a, T b){
    return (a*b)/gcd(a,b);
}

ll INF = 1e9+7;

template<class T>
void dcomb(T n,T m, string s){
    if(n==0) cout << s << endl;
    else {
        for(T i=0; i<m; ++i){
            dcomb(n-1,m,s+to_string(i));
        }
    }
}

int main(){
    ll h,n;
    cin >> h >> n;
    vector<ll> a(n), b(n);
    rep(i,n) cin >> a[i] >> b[i];
    vector<vector<ll>> dp(n+1,vector<ll>(h+1,INF));
    dp[0][0] = 0;
    rep(i,n){
        rep(j,h+1){
            chmin(dp[i+1][j],dp[i][j]);
            chmin(dp[i+1][min(h,j+a[i])],dp[i+1][j]+b[i]);
        }
    }
    cout << dp[n][h] << endl;
}

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


int main() {
	string s;
	cin >> s;
	for (int i = 0; i < 3; i++) {
		cout << s[i];
	}
}

Measured memory_bytes: 3620
N, M = map(int, input().split())
arr = []
for i in range(M):
    arr.append(int(input())) 

arr.append(10**10)

dp = [0 for i in range(N+1)]
dp[0] = 1

tmp = 0

if arr[0] == 1:
    dp[1] = 0
    tmp += 1
else:
    dp[1] = 1

for i in range(N-1):
    if arr[tmp] == i+2:
        dp[i+2] = 0
        tmp += 1
        continue
    dp[i+2] = dp[i+1] + dp[i]

print(dp[N]%(1000000007))

Measured memory_bytes: 460056
s=input()
n=len(s)
if s[0]=="<":
    nari=0
    scnt,dcnt=0,1
else:
    nari=1
    scnt,dcnt=1,0
ans=0
sfla,dfla=0,0
for i in range(n):
    if nari==0:
        if s[i]=="<":
            scnt+=1
        elif s[i]==">":
            ans+=scnt*(scnt-1)//2
            sfla=scnt
            nari=1
            scnt=1
            dlas=0

    elif nari==1:
        if s[i]==">":
            dcnt+=1
        elif s[i]=="<":
            ans+=dcnt*(dcnt-1)//2
            dfla=dcnt
            nari=0
            dcnt=1
            dlas=1
            ans+=(max(dfla,sfla))
    # print(ans)
if dcnt!=1:
    ans+=dcnt*(dcnt+1)//2
elif scnt!=1:
    ans+=scnt*(scnt+1)//2
else: ans+=1
print(ans)


Measured memory_bytes: 4232
#include <stdio.h>
#include<ctype.h>


int main()
{
	int a[3434],b,sum=0,n,i,j,k,t ;
    char ch ;
    scanf("%c",&ch) ;
if(isupper(ch))
    printf("A") ;
else if(islower(ch))
    printf("a") ;
	return 0;
}


Measured memory_bytes: 1596
#include <bits/stdc++.h>
using namespace std;
int main(){
	int N, K; 
	cin >> N >> K; 
	long long int A[100010] = {}; 
	long long int S[100010] = {}; //累積和
	long long int T[100010] = {}; //非負の項の累積和
	for(int i = 1; i <= N; i++){
		cin >> A[i]; 
		S[i] = S[i-1] + A[i];
		T[i] = T[i-1] + max(A[i], (long long) 0); 
	}
	long long int kuro = 0; //最終操作が黒
	long long int shiro = 0; //最終操作が白
	for(int i = 1; i <= N - K + 1; i++){
		long long int a = S[i + K - 1] - S[i - 1]; 
		long long int b = T[N] - T[i + K - 1] + T[i - 1]; 
		kuro = max(kuro, a + b); 
		shiro = max(shiro, b); 
	}
	cout << max(kuro, shiro) << endl; 
}

Measured memory_bytes: 2560
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<long long, int> P;
bool pairCompare(const P& firstElof, const P& secondElof)
{
    return firstElof.second > secondElof.second;
}

int main() {
    long long N, M; cin >> N >> M;

    priority_queue<P> A;
    //vector<long long> D;
    for(int i=0; i<N; i++) {
        long long tmp; cin >> tmp;
        A.push(make_pair(tmp, 1));
    }

    int B;
    long long C;
    for(int i=0; i<M; i++) {
        cin >> B >> C;
        A.push(make_pair(C, B));
    }


    long long ans = 0;
    for(int i=0;i < N; i++) {
        P tmp_P = A.top();
        A.pop();
        ans += tmp_P.first;
        if(tmp_P.second > 1) {
            tmp_P.second--;
            A.push(tmp_P);
        }
    }

    cout << ans << endl;

    return 0;
}



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

int main() {

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



Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 2e5+10;

int a[maxn];
bool vis[maxn];
int cnt[maxn];
int main()
{
	int n,ans=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=n;i;i--)
	{
		vis[a[i]]=1;
		if(vis[a[i]+1])
			cnt[a[i]]= cnt[a[i]+1]+1;
		else cnt[a[i]]=1;
		ans = max(ans,cnt[a[i]]);
	}
	printf("%d",n-ans);
	return 0;
}


Measured memory_bytes: 1920
#include <iostream>
#include <vector>
using namespace std;
struct ps{
    int wa=0;
    bool ac=false;
};

int main(void){
    // Your code here!
    int N,M;
    cin >> N >> M;
    vector<ps> PS(N);
    for (int i = 0; i<M; i++) {
        int p;
        string S;
        cin >> p >> S;
        if(!PS.at(p-1).ac && S == "WA")
            PS.at(p-1).wa++;
        if( S == "AC")
            PS.at(p-1).ac = true;
    }
    
    
    
    int num_wa = 0;
    int num_ac = 0;
    for (ps elem : PS){
        
        if (elem.ac){
            num_wa += elem.wa;
            num_ac++;
        }
    }
    cout << num_ac << ' ' << num_wa;
    
    
}

Measured memory_bytes: 1152
#include<bits/stdc++.h>
using namespace std;
#define lli long long int
const lli mod=1e9+7;
void fast() {std::ios::sync_with_stdio(false);cin.tie(NULL);}
lli power(lli a,lli b){lli ans=1;while(b!=0){ if(b%2==1){ans*=a;}b/=2;a*=a;} return ans;}
lli invmod(lli a) {return pow(a,mod-2);}
#define vi vector<int>
#define vlli vector<lli>
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define si(n) scanf("%d",&n)
#define sli(n) scanf("%lld",&n)
#define printi(n) printf("%d\n",n)
#define printli(n) printf("%lld\n",n)
#define all(vi) (vi.begin(),vi.end())
#define forn(i,n) for(int i=0;i<n;i++)
void print(int a[],int n){for(int i=0;i<n;i++) cout<<a[i]<<" ";}
bool vis[200005];

int main(){
    int n,m,x,y;
    si(n);si(m);
    bool ans=false;
    
    for(int i=0;i<m;i++){
        si(x);si(y);
        if(x==1){
            if(vis[y]) ans=true;
            vis[y]=true;
        }
        else if(y==n){
            if(vis[x]) ans=true;
            vis[x]=true;
        }
    }
    
    if(ans) cout<<"POSSIBLE\n";
    else cout<<"IMPOSSIBLE\n";
	return 0;
}

Measured memory_bytes: 384