akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>





using namespace std;



template < class BidirectionalIterator >
bool next_combination ( BidirectionalIterator first1 ,
  BidirectionalIterator last1 ,
  BidirectionalIterator first2 ,
  BidirectionalIterator last2 )
{
  if (( first1 == last1 ) || ( first2 == last2 )) {
    return false ;
  }
  BidirectionalIterator m1 = last1 ;
  BidirectionalIterator m2 = last2 ; --m2;
  while (--m1 != first1 && !(* m1 < *m2 )){
  }
  bool result = (m1 == first1 ) && !(* first1 < *m2 );
  if (! result ) {
    // テ「ツ堕?
    while ( first2 != m2 && !(* m1 < * first2 )) {
      ++ first2 ;
    }
    first1 = m1;
    std :: iter_swap (first1 , first2 );
    ++ first1 ;
    ++ first2 ;
  }
  if (( first1 != last1 ) && ( first2 != last2 )) {
    // テ「ツ堕。
    m1 = last1 ; m2 = first2 ;
    while (( m1 != first1 ) && (m2 != last2 )) {
      std :: iter_swap (--m1 , m2 );
      ++ m2;
    }
    // テ「ツ堕「
    std :: reverse (first1 , m1 );
    std :: reverse (first1 , last1 );
    std :: reverse (m2 , last2 );
    std :: reverse (first2 , last2 );
  }
  return ! result ;
}
 
template < class BidirectionalIterator >
bool next_combination ( BidirectionalIterator first ,
  BidirectionalIterator middle ,
  BidirectionalIterator last )
{
  return next_combination (first , middle , middle , last );
}


int main(){
  while(1){
    int n,k; cin >> n >> k;
    if(n==0 && k==0) break;
    vector<string> ss;
    set<string> hoge;
    for(int i=0; i<n; i++){
      string x; cin >> x;
      ss.push_back(x);
    }
    sort(ss.begin(),ss.end());
    
    do{
      vector<string> maki;
      for(int i=0; i<k; i++) maki.push_back(ss[i]);
      do{
	string tmp="";
	for(int i=0; i<maki.size(); i++)
	  tmp += maki[i];
	hoge.insert(tmp);
      }while(next_permutation(maki.begin(),maki.end()));
    }while(next_combination(ss.begin(), ss.begin()+k, ss.end()));
    cout << hoge.size() << "\n";
  }
}

Measured memory_bytes: 1468
input_line = input()
A,B = [int(s) for s in input_line.split(' ')]

def price(A,B):
    if A >= 13:
        print(B)
    elif 6 <= A <=12:
        print(int(B/2))
    elif 5 >= A:
        print('0')
        
price(A,B)

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

int main() {
  int64_t X, K, D;
  scanf("%lld %lld %lld", &X, &K, &D);
  int64_t num = std::min(K, std::abs(X) / D);
  X = X + (X > 0 ? -num * D : num * D);
  if ((K - num) % 2) {
    int64_t up = X + D;
    int64_t down = X - D;
    if (std::abs(up) < std::abs(down))
      X = up;
    else X = down;
  }
  printf("%lld\n", std::abs(X));
}


Measured memory_bytes: 3824
#include <iostream>
using namespace std;
int main()
{
    int a = 0;
    int b = 0;
    cin >> a >> b;
    int i = 0;
    int g = 0;
    int output = 0;
    int flag = 0;
    if(a > b)
    {
        i  = a - b;
        i = i / 2;
        for(g = 0;g < i;g++)
        {
            a = a - 1;
            b = b + 1;
            if(b + 1 == a)
            {
                output = b + 1;
                flag = 1;
                break;
            }
            else if(b == a)
            {
                flag = 1;
                output = b;
                break;
            }
        }
    }
    else if(a < b)
    {
        i = b - a;
        i = i / 2;
        for(g = 0;g < i;g++)
        {
            b = b - 1;
            a = a + 1;
            if(a + 1 == b)
            {
                output = a + 1;
                flag = 1;
                break;
            }
            else if(a == b)
            {
                flag = 1;
                output = a;
                break;
            }
        }
    }
    else
    {
        cout<<a;
    }
    if(flag == 1)
    {
        cout<<output;
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
 
vector<int> v;
vector<string> u;
void solve(int i, int n, string ans) {
    if(i==4) {
        if(n==7) {
            u.push_back(ans);
        }
        return;
    }
    for(int j=0; j<2; ++j) {
        solve(i+1, n+v[i], ans+"+");
        solve(i+1, n-v[i], ans+"-");
    }
}
 
signed main() {
    string s;
    cin >> s;
    for(int i=0; i<s.size(); ++i) v.push_back(s[i]-'0');
    solve(1, v[0], "");
    string ans = u[0];
    cout << v[0] << ans[0] << v[1] << ans[1] << v[2] << ans[2] << v[3] << "=7" << endl;
    return 0;
}


Measured memory_bytes: 256
from collections import deque
from collections import Counter
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right, bisect
#pypyではscipy, numpyは使えない
#from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, minimum_spanning_tree
#from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
import numpy as np
from fractions import gcd
from math import ceil,floor, sqrt, cos, sin, pi, factorial, log, log10, log2
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
from datetime import datetime as dt

def main():
  n = int(readline())
  A=list(map(int, readline().split()))
  B = [0]*n
  for shusseki, rank in enumerate(A):
    B[rank-1] = shusseki + 1
  print(' '.join(map(str, B)))
  
  
  
  
if __name__ == '__main__':
  main()

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

using namespace std;
#define ll long long int
#define rep(i,n) for(i=0;i<(n);i++)
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define all(c) c.begin(),c.end()
#define endl "\n"
typedef pair< ll, ll > lpair;

bool sortbysec(const pair<int,int> &a, const pair<int,int> &b)
{
    if(a.ff == b.ff)
        return (a.ss < b.ss);
    return (a.ff < b.ff);
}

vector< ll > prime(1000005,1);
void p()
{
    ll i,j;
    for(i=2;i<=1000000;i++)
    {
        if(prime[i] == 1)
        {
            for(j = 2*i;j<=1000000;j+=i) prime[j] = 0;
        }
    }
}

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

    ll n,i,j;
    cin>>n;
    vector< ll > a(n+1),b(n+1),c(n+1);
    rep(i,n)
    {
        cin>>a[i+1]>>b[i+1]>>c[i+1];
    }
    ll dp[4][n+1];
    dp[1][1] = a[1];
    dp[2][1] = b[1];
    dp[3][1] = c[1];

    ll k;
    for(i = 2;i<=n;i++)
    {
        dp[1][i] = max(dp[2][i-1],dp[3][i-1]) + a[i];
        dp[2][i] = max(dp[1][i-1],dp[3][i-1]) + b[i];
        dp[3][i] = max(dp[2][i-1],dp[1][i-1]) + c[i];
    }
    cout<<max(dp[1][n],max(dp[2][n],dp[3][n]))<<endl;
} 


Measured memory_bytes: 12800
#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>

using namespace std;

#define FOR(i,k,n) for(int i=(k); i<(int)n; ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cout<<*i<<" "; cout<<endl; }

typedef long long ll;
const int INF = 100000000;
const double EPS = 1e-8;
const int MOD = 1000000007;
struct Node{
  int cnt;
  Node* children[2];
  Node() : cnt(1) {
    memset(children, 0, sizeof(children));
  }
};
struct Result{
  Node* value;
  int t;
  Result(Node* p, int t) : value(p), t(t) {}
};
Result parse(Node* p, const string& s, int t = 0){
  if(p == NULL) p = new Node();
  else p->cnt ++;
  assert(s[t] == '(');
  if(s[t + 1] != ','){
    Result r1 = parse(p->children[0], s, t + 1);
    p->children[0] = r1.value;
    t = r1.t;
  }else{
    t ++;
  }
  assert(s[t] == ',');
  if(s[t + 1] != ')'){
    Result r2 = parse(p->children[1], s, t + 1);
    p->children[1] = r2.value;
    t = r2.t;
  }else{
    t++;
  }
  assert(s[t] == ')');
  return Result(p, t + 1);
}
void print(Node *p, int B){
  if(p == NULL) return;
  if(p->cnt < B) return;
  printf("(");
  print(p->children[0], B);
  printf(",");
  print(p->children[1], B);
  printf(")");
}
int main(){
  while(true){
    char c; cin >> c;
    if(cin.eof()) break;
    string s;
    cin >> s;
    Result r = parse(NULL, s);
    Node* root = r.value;
    assert(r.t == s.size());
    cin >> s;
    Result r2 = parse(root, s);
    print(root, (c == 'i') ? 2 : 1);
    cout << endl;
  }
  return 0;
}

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

void solve(long long P, long long Q, long long R)
{
    vector<long long> A = {P, Q, R};
    long long M = P + Q + R;

    M = min(M, A[0] + A[1]);
    M = min(M, A[0] + A[2]);
    M = min(M, A[1] + A[2]);

    cout << M << endl;
}

// Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main()
{
    long long P;
    scanf("%lld", &P);
    long long Q;
    scanf("%lld", &Q);
    long long R;
    scanf("%lld", &R);
    solve(P, Q, R);
    return 0;
}


Measured memory_bytes: 256
while True:
    num = int(input())
    if num == 0:
        break
    
    L = [0]*num
    F = 0
    
    cnt = 0
    for i in input():
        L[cnt] += 1
        if i == "M":
            pass
        elif i == "S":
            F += L[cnt]
            L[cnt] = 0
        else:
            L[cnt] += F
            F = 0
        cnt += 1
        cnt %= num
    
    print(*sorted(L), F)
        
    


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

typedef long long ll;
int n,k;
vector<ll> v;
int min1 = 1e9;
ll func(ll key){
    ll k = 0;
    for(int i = 0;i<n;i++){
        k += ceil((double) v[i]/key) - 1;
    }
    return k;
}

ll binary_search(){
    ll left = 0;
    ll right = 1e9 ;
    while(right - left > 1){
        ll mid = (left + right)>> 1;
        if(func(mid) <= k) right = mid;
        else left = mid;
    }
    return right;
}
int main(){
    cin >> n >> k;
    for(int i = 0;i<n;i++){
        ll tmp;
        scanf("%lld",&tmp);
        v.push_back(tmp);
    }
    cout << binary_search() << endl;
    return 0;
}

Measured memory_bytes: 5436
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll w,h,x,y;
    cin>>w>>h>>x>>y;
    double tot=w*h;
    tot/=2;
    cout<<tot<<" ";
    if(x*2==w&&y*2==h)cout<<1;
    else
    cout<<0;
    return 0;
}

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

using ll = long long;
using ld = long double;
using vi = vector<int>;
using vll = vector<ll>;
using P = pair<int, int>;

const int INF = 1e9;
const ll INFLL = 1e18;
const int MOD = 1e9 + 7;
const int NIL = -1;
const ld PI = acos(-1);

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

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 (b<a) { a=b; return 1; } return 0; }

#define DEBUG

int main()
{
	ios::sync_with_stdio(false); cin.tie(nullptr);
	//cout << fixed << setprecision(6);
	int n, x;
	cin >> n >> x;
	vi l(n);
	rep(i, n) cin >> l[i];

	int ans = 1;
	vi d(n+1, 0);
	for(int i = 1; i <= n; i++)
	{
		d[i] = d[i-1] + l[i-1];
		if(d[i] <= x) ans++;
	}

	rep(i, d.size()) cerr << d[i] << ' ';
	cerr << endl;

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

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
int a[N];
const int mod = 1e9+7;
ll qmi(ll a,ll k) {
	ll res = 1;
	while(k) {
		if(k&1) {
			res = res*a%mod;
		}
			a=a*a%mod;
			k>>=1;
	}
	return res;
}
int main() {
	ll n;
	cin>>n;
	ll ans = ((qmi(10,n)%mod+mod+qmi(8,n)%mod)%mod+mod-2*qmi(9,n)%mod)%mod;
	cout<<ans<<endl;
    return 0;
} 

Measured memory_bytes: 3616
import java.util.Scanner;

class Main{
    
    public static void main(String[] args){
        
        Scanner sc = new Scanner(System.in);
        
        int W = sc.nextInt();
        int H = sc.nextInt();
        int x = sc.nextInt();
        int y = sc.nextInt();
        int r = sc.nextInt();
        
        if(x+r <= W && y+r <= H && x-r >= 0 && y-r >= 0){
            System.out.println("Yes");
        }else{
            System.out.println("No");
        }
    }
}


Measured memory_bytes: 26404
#include <stdio.h>
#include <algorithm>
#include <assert.h>
#include <bitset>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits.h>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <time.h>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:336777216")
using namespace std;

#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define ldb ldouble

typedef tuple<int, int, int> t3;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;

int IT_MAX = 1 << 19;
int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const db PI = acos(-1);
const db ERR = 1e-10;
#define szz(x) (int)(x).size()
#define rep(i, n) for(int i=0;i<n;i++)
#define Se second
#define Fi first

const int MX = 200005;
const int MM = 1000000007;

int N, M;
int D[MX], E[MX];

vector<int> G[MX];

void dfs(int x, int p, int D[MX]){
	D[x] = D[p] + 1;
	for(int c : G[x]){
		if( c == p ) continue;
		dfs(c, x, D);
	}
}

int main()
{
	scanf("%d", &N);
	for(int i = 1; i < N; i++){
		int a, b;
		scanf("%d%d", &a, &b);
		G[a].push_back(b);
		G[b].push_back(a);
	}
	dfs(1, 0, D);
	dfs(N, 0, E);
	int ans = 0;
	for(int i = 1; i <= N; i++){
		ans += D[i] <= E[i] ? 1 : -1;
	}
	if( ans >= 1 ) printf("Fennec\n");
	else printf("Snuke\n");
}


Measured memory_bytes: 14208
#include <bits/stdc++.h>
using namespace std;
#define int long long

int n, a[100100], dams[100100];
int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    int sum = 0, evensum = 0;
    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
        sum += a[i];
        if (i % 2 == 0) evensum += a[i];
    }
    dams[1] = sum - (evensum * 2); 
    for(int i = 2; i <= n; ++i) {
        dams[i] = a[i-1] * 2 - dams[i-1];
    }
    for(int i = 1; i <= n; ++i) {
        cout << dams[i] << ' ';
    }
}


Measured memory_bytes: 5200
#include<bits/stdc++.h>
#define rep(i, n) for (int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
 
int main(void){
    int n;
    ll t;
    cin>>n>>t;
    vector<ll> v(n);
    rep(i, n) cin>>v[i];
    ll ans = 0;
    rep(i, n-1){
        ans += min(t, v[i+1]-v[i]);
    }
    ans += t;
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 1792
#include <algorithm>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <vector>
#include <list>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
//#define cerr if(false) cerr
#ifdef DEBUG
#define show(...) cerr << #__VA_ARGS__ << " = ", debug(__VA_ARGS__);
#else
#define show(...) 42
#endif
using namespace std;
using ll = long long;
using pii = pair<int, int>;
template <typename T, typename S>
ostream& operator<<(ostream& os, pair<T, S> a) {
    os << '(' << a.first << ',' << a.second << ')';
    return os;
}
template <typename T>
ostream& operator<<(ostream& os, vector<T> v) {
    for (auto x : v) os << x << ' ';
    return os;
}
void debug() {
    cerr << '\n';
}
template <typename H, typename... T>
void debug(H a, T... b) {
    cerr << a;
    if (sizeof...(b)) cerr << ", ";
    debug(b...);
}
void chmin(ll &a, ll b){
    a = min(a,b);
}
ll dp[305][305][305];
int main(){
    int n, K;
    cin >> n >> K;
    vector<ll> h(n+1);
    rep(i,n)cin >> h[i+1];
    rep(i,n+1)rep(j,K+1)rep(k,n+1)dp[i][j][k] = 1LL<<60;
    dp[0][0][0] = 0;
    h[0] = 0;
    rep(i,n){
        rep(j,K+1){
            for(int k = 0; k <= i; k++){
                if(dp[i][j][k] == 1LL<<60)continue;
                if(j < K){
                    chmin(dp[i+1][j+1][k],dp[i][j][k]);
                }
                if(h[k] < h[i+1]){
                    chmin(dp[i+1][j][i+1],dp[i][j][k]+h[i+1]-h[k]);
                }else if(h[k]==h[i+1]){
                    chmin(dp[i+1][j][k],dp[i][j][k]);
                }else if(h[k] > h[i+1]){
                    chmin(dp[i+1][j][i+1],dp[i][j][k]);
                }
            }
        }
    }
    ll ans = 1LL<<60;
    rep(j,K+1)rep(k,n+1)ans = min(ans, dp[n][j][k]);
    cout << ans << endl;
}


Measured memory_bytes: 219392
/// ببِسْمِ اللَّهِ الرَّحْمَنِ الرَّحِيم
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
     ios_base::sync_with_stdio(false);cin.tie(NULL);
     ll int i,n,t,p=INT_MAX,j=0,x,a=0,b,l=0,r=0,y,k,c,sum=0;
     string s,m;
     cin>>n>>k;
    vector<int>ara;
     for(i=0;i<k;i++){
        cin>>p;
       ara.push_back(p);
     }
     sort(ara.begin(),ara.end());
     for(i=0;i<k-1;i++){
        l=ara[i+1]-ara[i];
        r=max(r,l);
     }
     a=n+ara[0];
     r=max(r,a-ara[k-1]);
     cout<<n-r<<endl;

     return EXIT_SUCCESS;
}



Measured memory_bytes: 1400
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 666666
set<int> s[66];
signed main(){
	int n;
	cin>>n;
	for(int i=0;i<=30;i++) s[i].insert(n);
	string str;
	cin>>str;
	for(int i=0;i<str.size();i++) s[str[i]-'a'].insert(i);
	int m;
	cin>>m;
	for(int i=0;i<m;i++){
		int op;
		cin>>op;
		if(op==1){
			int pos;
			char ch;
			cin>>pos>>ch;
			pos--;
			if(ch==str[pos]) continue;
			s[str[pos]-'a'].erase(pos);
			str[pos]=ch;
			s[ch-'a'].insert(pos);
		}else{
			int l,r;
			cin>>l>>r;
			int ans=0;
			l--;
			r--;
			for(int j=0;j<26;j++){
				int pos=*s[j].lower_bound(l);
				if(pos<=r) ans++;
			} 
			cout<<ans<<'\n';
		}
	}
	return 0;
}

Measured memory_bytes: 24240
#include<bits/stdc++.h>
 
using namespace std;
#define ll long long int
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define reps(X,S,Y) for (int (X) = S;(X) < (Y);++(X))
#define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X))
#define rreps(X,S,Y) for (int (X) = (Y)-1;(X) >= (S);--(X))
#define repe(X,Y) for ((X) = 0;(X) < (Y);++(X))
#define toit ios::sync_with_stdio(0);cin.tie(0);
 

int main()
{toit
    int n;
    cin>>n;
    string s1="",s2="";
    rep(i,n){
        char a;
        cin>>a;
        s1+=a;
    }
    rep(i,n){
        char a;
        cin>>a;
        s2+=a;
    }
    string t = "";
    char cf= '1';
    rep(i,n){
        t = t+cf;
        cf++;
    }
    int c=0,x=0,a=0,b=0;
    while(x<2){
        if(s1.compare(t)==0){
            a=c;
            x++;
        }
        if(s2.compare(t)==0){
            b=c;
            x++;
        }
        c++;
        next_permutation(t.begin(), t.end());
        
    }
    cout<<abs(a-b);
    return 0;
}


Measured memory_bytes: 256
//██████╗ ██╗   ██╗██╗      ██████╗ ███████╗
//██╔══██╗██║   ██║██║      ██╔══██╗██╔════╝
//██████╔╝██║   ██║██║█████╗██║  ██║█████╗
//██╔══██╗██║   ██║██║╚════╝██║  ██║██╔══╝
//██║  ██║╚██████╔╝██║      ██████╔╝███████╗
//╚═╝  ╚═╝ ╚═════╝ ╚═╝      ╚═════╝ ╚══════╝
#include <iostream>
#include <random>
#include <vector>
#include <set>
#include <algorithm>
#include <iomanip>
#include <chrono>
#include <cstdio>
#include <map>
#include <memory.h>


// #pragma GCC target("sse,sse2,sse3,ssse3,sse4")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;

#define fst first
#define snd second
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back

#define all(v) (v).begin(), (v).end()
#define sz(v) ((int)(v).size())
#define sqr(x) ((x) * (x))

typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef vector<int> vi;

#define next ajksdslk
#define prev aklsfjk

mt19937_64 mt_rand(chrono::system_clock::now().time_since_epoch().count());

template<typename T1, typename T2> inline bool upmax(T1& a, T2 b) { return (a < b ? (a = b, true) : false); }
template<typename T1, typename T2> inline bool upmin(T1& a, T2 b) { return (b < a ? (a = b, true) : false); }

const int maxn = (int) 5e6 + 100;
const int maxlog = 21;
const int base = 1e9 + 7;
const ld eps = (ld) 1e-9;
const ld PI = acos(-1.);
//const int pp = 41;
const int inf = 2e9;
const ll llinf = 1e18;

ll f[333][333][333];
ll dist[maxn];

void amin(ll& a, ll b) {
  if (a == -1) a = b;
  else {
    upmin(a, b);
  }
}

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

  int n, k;
  cin >> n >> k;
  vector<int> h(n);
  map<int,int> mm;
  for (int i = 0; i < n; i ++) {
    cin >> h[i];
    mm[h[i]] = 42;
  }
  int N = 0;
  int pred = 0;

  for (auto& it : mm) {
    it.second = ++N;
    dist[N] = it.first;

  }
  for (int i = 0; i < n; i ++) {
    h[i] = mm[h[i]];
  }
  for (int i = 0; i <= n; i ++) {
    for (int j = 0; j <= k; j ++) {
      for (int c = 0; c <= N; c ++) {
        f[i][j][c] = llinf;
      }
    }
  }
  f[0][0][0] = 0;
  for (int i = 0; i < n; i ++) {
    for (int c = 0; c <= k; c ++) {

      vector<ll> suff(N + 1, 0), pref(N + 1, 0);
      for (int curH = 0; curH <= N; curH ++) {
        pref[curH] = f[i][c][curH] - dist[curH];
        suff[curH] = f[i][c][curH];
        if (curH) upmin(pref[curH], pref[curH - 1]);
      }
      for (int curH = N - 1; curH >= 0; curH --){
        upmin(suff[curH], suff[curH + 1]);
      }


      for (int nxtH = 0; nxtH <= N; nxtH ++) {
        ll add = min(pref[nxtH] + dist[nxtH], suff[nxtH]);

        if (nxtH == h[i]) {
          upmin(f[i + 1][c][nxtH],  add);
        } else{
          upmin(f[i + 1][c + 1][nxtH], add);
        }
      }

    }
  }
  ll ans = -1;
  for (int i = 0; i <= k; i ++) {
    for (int j = 0; j <= N; j++) {
      amin(ans, f[n][i][j]);
    }
  }
  cout << ans << "\n";
  return 0;
}

Measured memory_bytes: 264320
/* 
AUTHOR : @Sam_Jn
*/
//lo + 1, hi, ret lo
#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
using namespace std;
// using namespace __gnu_pbds;
// typedef tree<pair<int, int>, null_type, less_equal<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
#define boost ios_base::sync_with_stdio(false); cin.tie(NULL);
#define ll long long
#define MOD 1000000007
#define pb push_back
#define ff first
#define ss second
#define NN 1000002
#define in(a, n) for(int i = 0; i < n; i++) cin >> a[i];
#define ot(a, n) for(int i = 0; i < n; i++) cout << a[i] << " ";
#define ot2(a, n) for(int i = 0; i < n; i++) cout << a[i] << "\n";
ll pwr(ll a, ll b);
ll pwr(ll a, ll b, ll m);
int baap[200002];
int prime[NN];
int find(int i);  
bool Union(int x, int y);
ll inv(ll x) {return pwr(x, MOD - 2, MOD);}
void init();
ll max(ll x, ll y, ll z) {return max(x, max(y, z));}
int dx[8] = {0, 0, 1, -1, 1, 1, -1, -1};
int dy[8] = {-1, 1, 0, 0, 1, -1, 1, -1};
//----------------------------------SOLUTION-BELOW-------------------------------------------// 

void solve(){

    string s;
    cin >> s;
    ll sum = 0;
    int n = s.size();
    for(int i = 0; i < n; i++){
        sum += (s[i] - '0');
        sum %= 9;
    }
    if(sum == 0) cout << "Yes";
    else cout << "No";
    // cout << e;
}
int main(){


                                                            #ifndef ONLINE_JUDGE    
                                                            freopen("../../input.txt", "r", stdin);
                                                            freopen("../../output.txt", "w", stdout);
                                                            #else
                                                            // online submission
                                                            #endif
// 

    boost
    int _ = 1;
    // cout << 0 << endl;
    // cin >> _;
    while(_--){
        solve();
        cout << endl;
    }
}
 
 
//--------------------------------------DEFININTIONS---------------------------------------
ll pwr(ll a, ll b){
    if(b == 0)
        return 1 ;
    ll c = pwr(a, b/2) ;
    c = c * c;
    if(b % 2)
        return c*a;
    return c ;
}
ll pwr(ll a, ll b, ll m){
    if(b == 0)
        return 1;
    ll c = pwr(a, b/2, m) % m ;
    c = (c * c) % m;    
    if(b % 2)
        return (c * a%m) % m;
    return c ;
}
int find(int i)  
{  
    if (baap[i] != i)  
        baap[i] = find(baap[i]);  
  
    return baap[i];  
}
 
bool Union(int x, int y)
{
    x = find(x);
    y = find(y);
    if(x == y) return false;
    baap[x] = y;
    return true;
}
void init(){
  for(ll i = 2; i < NN; i++){
      if(prime[i]) continue;
      for(ll j = 2*i; j < NN; j += i)
          prime[j] = i;
  }
}

Measured memory_bytes: 3772
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		@SuppressWarnings("resource")
		Scanner stdin = new Scanner(System.in);

		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < 3; i++) {
			String line = stdin.next();
			sb.append(line.charAt(i));
		}

		System.out.print(sb.toString());
	}

}


Measured memory_bytes: 21712
#include<stdio.h>
int main()
{
    int n,a[2];
    for(n=0;n<2;n++)
    {
        scanf("%d",&a[n]);
    }
    if(a[0]==1&&a[1]==2||a[0]==2&&a[1]==1)
    {
        printf("3");
    }
    if(a[0]==2&&a[1]==3||a[0]==3&&a[1]==2)
    {
        printf("1");
    }
    if(a[0]==1&&a[1]==3||a[0]==3&&a[1]==1)
    {
        printf("2");
    }
    return 0;
}


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

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

  bool result = (A == B && A != C)
  || (A == C && A != B)
  || (B == C && A != B);

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int n,a[20],m,i,x;
int dfs(int y,int p){
  if(p==0)return 1;
  if(y>=n)return 0;
  int q=dfs(y+1,p)||dfs(y+1,p-a[y]);
  return q;
}
int main(){
  for(cin>>n;i<n;i++)cin>>a[i];
  for(cin>>m,i=0;i<m;i++){
    cin>>x;
    if(dfs(0,x))cout<<"yes"<<endl;
    else cout<<"no"<<endl;
  }
}

Measured memory_bytes: 3092
object Main {
  def main(args: Array[String]): Unit = {
    solve
  }

  def solve(): Unit = {
    val sc = new java.util.Scanner(System.in)
    val n = sc.nextInt
    var m = sc.nextInt
    val pq = collection.mutable.PriorityQueue[Long]()
    for (i <- 0 until n) {
      pq.enqueue(sc.nextLong())
    }

    // 最後に合計出せばいいのか
    //    var sum = pq.toList.sum
    while (m > 0) {
      val max = pq.dequeue()
      val half = max / 2
      //      sum -= max - tmp
      pq.enqueue(half)
      m -= 1
    }

    println(pq.toList.sum)
  }
}


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

int main(){
  int N,K;
  cin>>N>>K;
  vector<int> price(N);
  for(int i=0;i<N;i++){
    cin >> price.at(i);
  }
  sort(price.begin(),price.end());
  int ans=0;
  for(int i=0;i<K;i++){
    ans += price.at(i);
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 3632
#include <cstdio>
#include <algorithm>
using namespace std;

int main()
{
  int a, b, c, d;
  std::scanf("%d %d %d %d", &a, &b, &c, &d);
  int ans = std::min(a, b) + std::min(c, d);
  std::printf("%d\n", ans);
  return 0;
}

Measured memory_bytes: 128
use std::io::prelude::*;
use std::io::stdin;
use std::str::FromStr;

fn main() {
    let mut abc: Vec<i32> = (0..3).map(|_| read()).collect();
    abc.sort();
    println!("{}", abc[0] + abc[1]);
}

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let token: String = stdin
        .lock()
        .bytes()
        .map(|b| b.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().unwrap()
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
char S[309][309];
main(){
    int n;
    cin >> n;
    for (int i= 0; i < n; i++){
        for (int j =0; j < n; j++){
            cin >> S[i][j];
        }
    }
    int ans = 0;
    for (int d = 0; d < n; d++){
        int fl = n;
        for (int i =0; i < n; i++){
            for (int j =0; j < n; j++){
                char X = S[i][(j+d)%n];
                char Y = S[j][(i+d)%n];
                if(X != Y) fl =0;
            }
        }
        ans += fl;
    }
    cout << ans << endl;

}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
     
const int MAX_N = 200000;
int n, k;
double p[MAX_N];
double e[MAX_N];

void solve() {
    for (int i = 0; i < n; i++) {
        e[i] = (p[i] + 1) / 2;
    }

    double s[n];
    s[0] = e[0];
    for (int i = 1; i < n; i++) {
        s[i] = s[i - 1] + e[i];
    }

    double ans[n - k + 1];
    double max = ans[0] = s[k - 1];
    for (int i = 1; i < n - k + 1; i++) {
        ans[i] = s[i + k - 1] - s[i - 1];
        if (ans[i] > max) {
            max = ans[i];
        }
    }

    printf("%.10f\n", max);
}

int main() {
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> p[i];
    }
    solve();
}

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

struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;
#define NIL NULL

Node root;

Node treeMinimum(Node x){
  while(x->left!=NIL){
  x=x->left;
  }
  return x;
}

Node treeMaximum(Node x){
  while(x->right!=NIL){
    x=x->right;
  }
  return x;
}

Node treeSearch(Node u, int k){
  if(u==NIL||k==u->key){
    return u;
  }
  if(k<u->key){
    return treeSearch(u->left,k);
  }
  else return treeSearch(u->right,k);
}

Node treeSuccessor(Node x){
  if(x->right!=NIL){
    return treeMinimum(x->right);
  }
  Node y;
  y=x->parent;
  while(y!=NIL && x==y->right){
    x=y;
    y=y->parent;
  }
  return y;
}

void treeDelete(Node z){
  Node y; // node to be deleted
  Node x; // child of y
}

void insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;

  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;

  while(x!=NIL){
    y=x;
    if(z->key < x->key){
      x=x->left;
    }
    else{
      x=x->right;
    }
  }
  z->parent=y;

  if(y==NIL){
    root=z;
  }
  else if(z->key < y->key){
    y->left=z;
  }
  else{
    y->right=z;
  }
}

void inorder(Node u){
  if(u==NIL){
    return;
  }
  inorder(u->left);
  printf(" %d",u->key);
  inorder(u->right);
}
void preorder(Node u){
  if(u==NIL){
    return;
  }
  printf(" %d",u->key);
  preorder(u->left);
  preorder(u->right);
}


int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);

  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'f' ){
      scanf("%d", &x);
      Node t = treeSearch(root, x);
      if ( t != NIL ) printf("yes\n");
      else printf("no\n");
    } else if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    } else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    } else if ( com[0] == 'd' ){
      scanf("%d", &x);
      treeDelete(treeSearch(root, x));
    }
  }

  return 0;
}


Measured memory_bytes: 25164
// V solo
#include <bits/stdc++.h>

#define forn(i, a, b) for (int i = a; i <= b; ++i)
#define forr(i, a, b) for (int i = a; i >= b; --i)

using namespace std;

const int N = (int)3e5 + 1;
const int INF = 1e9 + 7;

typedef long long ll;
typedef long double ld;

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

int n, ans[N];
pii a[N];
int main (){
  scanf ("%d", &n);
  forn (i, 1, n){
    scanf ("%d", &a[i].first);
    a[i].second = i;
  }
  sort (a + 1, a + n + 1);
  int l = n / 2;
  forn (i, 1, n){
    if (i <= l) ans[a[i].second] = a[l + 1].first;
    else ans[a[i].second] = a[l].first;
  }
  forn (i, 1, n) printf ("%d\n", ans[i]);
  return 0;
}

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

int main(){
	int n;
	cin >> n;
	for (; n <= 999; ++n) {
		if (n%10 == n/100 && n/10%10 == n%10) {
			printf("%d", n);
			return 0;
		}
	}
}

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

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl




typedef long long ll;
const ll mod = 1e9+7;
const int maxn = 1e6 + 5;


int n;
string s;
int a[maxn];
int prefix[maxn][3];
ll ans = 0;
int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);
    cin>>n>>s;
    for (int i=0; i<n; i++) {
	if (s[i]=='R') a[i]=0;
	if (s[i]=='G') a[i]=1;
	if (s[i]=='B') a[i]=2;
    }

    for (int i=0; i<n; i++) {
	prefix[i][a[i]]++;
	for (int j=0; j<3; j++) {
	    if (i) {
		prefix[i][j] += prefix[i-1][j];
	    }
	}
    }

    // for (int i=0; i<n; i++) {
    // 	cout<<a[i]<<" ";
    // }
    // cout<<endl;

    for (int i=0; i<n; i++) {
	for (int j=i+1; j<n; j++) {
	    if (a[i] != a[j]) {
		//cout<<i<<" "<<j<<endl;
		int other = 0;
		while (other == a[i] || other == a[j]) ++other;
		int match = prefix[n-1][other] - prefix[j][other];
		int dist = j-i;
		if (j+dist < n && a[j+dist] == other) match--;
		ans += match;
	    }
	}
    }

    cout<<ans<<endl;

    return 0;
}


Measured memory_bytes: 3668
N = int(input())
lCnt = {}
for n in range(N):
  i = n + 1
  lCnt[i] = 0
i = 2
for n in input().split():
  Ai = int(n)
  lCnt[Ai] += 1
  i += 1
for n in lCnt:
  print(lCnt[n])

Measured memory_bytes: 98944
//{{{
#include <bits/stdc++.h>
using namespace std;
#define repX(a,b,c,x,...) x
#define repN(a) repX a
#define rep(...) repN((__VA_ARGS__,rep3,rep2,loop))(__VA_ARGS__)
#define rrep(...) repN((__VA_ARGS__,rrep3,rrep2))(__VA_ARGS__)
#define loop(n) rep2(i_,n)
#define rep2(i,n) rep3(i,0,n)
#define rep3(i,begin,end) for(int i=(int)(begin),i##_end=(int)(end);i<i##_end;++i)
#define rrep2(i,n) rrep3(i,n,0)
#define rrep3(i,begin,end) for(int i=(int)(begin-1),i##_end=(int)(end);i>=i##_end;--i)
#define foreach(x,a) for(auto&x:a)
using ll=long long;
const ll MOD=(ll)1e9+7;
//}}}

int main(){
  string s;
  ll K;
  cin >> s >> K;
  char ans;
  if(K <= 100){
    bool f = false;
    rep(i, K){
      if(s[i] != '1'){
        ans = s[i];
        f = true;
        break;
      }
    }
    if(!f){
      ans = '1';
    }
  }else{
    rep(i, s.size()){
      if(s[i] != '1'){
        ans = s[i];
        break;
      }
    }
  }
  cout << ans << endl;
  return 0;
}


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

using namespace std;
typedef long long ll;

template <class T> inline void read(T &x) {
	char ch; bool flag = false;
	while (!isdigit(ch = getchar())) flag |= ch == '-';
	for (x = ch ^ 48; isdigit(ch = getchar()); x = x * 10 + (ch ^ 48));
	if (flag) x = -x;
}

inline int input() {
	int x; char ch; bool flag = false;
	while (!isdigit(ch = getchar())) flag |= ch == '-';
	for (x = ch ^ 48; isdigit(ch = getchar()); x = x * 10 + (ch ^ 48));
	return flag ? -x : x;
}

const int mod = 1e9 + 7;
inline int add(int x, int y) { x += y; return x >= mod ? x - mod : x; }
inline void inc(int &x, int y) { x += y; x -= x >= mod ? mod : 0; }

inline int Power(int x, int y) {
	int res = 1;
	while (y) {
		if (y & 1) res = (ll) res * x % mod;
		x = (ll) x * x % mod, y >>= 1;
	} return res;
}

template <class T> void chkmax(T &x, T y) { x = x > y ? x : y; }
template <class T> void chkmin(T &x, T y) { x = x < y ? x : y; }
template <class T> T gcd(T x, T y) { return !y ? x : gcd(x % y, y); }

int n, fa[N], val[N];
int f[N], g[N];

struct DSU {
	int fa[N];
	void init(int n) { for (int i = 1; i <= n; ++i) fa[i] = i; }
	int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
	void merge(int x, int y) {
		x = find(x), y = find(y);
		f[y] += f[x], g[y] += g[x];
		fa[x] = y;
	}
}S;

struct Node { int x; };
inline bool operator < (const Node &x, const Node &y) {
	ll A = (ll) f[x.x] * g[y.x], B = (ll) f[y.x] * g[x.x];
	if (A == B) return x.x < y.x;
	else return A > B;
}
set<Node> Set;

int main() {
	ios::sync_with_stdio(false);
	cin >> n, S.init(n);
	for (int i = 2; i <= n; ++i) cin >> fa[i];
	for (int i = 1; i <= n; ++i) {
		cin >> val[i];
		if (val[i] == 1) ++g[i];
		else ++f[i];
	}
	
	ll ans = 0;
	for (int i = 2; i <= n; ++i) Set.insert({i});
	while (!Set.empty()) {
		int now = S.find(Set.begin()->x);
		Set.erase(Set.begin());
		int Fa = S.find(fa[now]);
        ans += (ll) g[Fa] * f[now];
		Set.erase({Fa}), S.merge(now, Fa);
		if (Fa != 1) Set.insert({Fa});
	}
	
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 13568
#include <stdio.h>
int main() {
    int m,n;
    int A[100][100];
    int b[100];
    int c[100];
    int i,j;
    scanf("%d %d",&n,&m);
    for(i=0; i<n; i++)
        for(j=0;j<m;j++)
            scanf("%d",&A[i][j]);
    for(i=0; i<m; i++)
        scanf("%d",&b[i]);
    
    for(i=0; i<n ; i++){
        c[i] = 0;
        for(j=0;j<m;j++){
        c[i] += A[i][j]*b[j];
        }
    }
    for(i=0;i<n;i++){
        printf("%d\n",c[i]);
    }
}


Measured memory_bytes: 2148
using System;
using System.Linq;
using CompLib.Util;

public class Program
{
    int A;
    long B, N;
    public void Solve()
    {
        var sc = new Scanner();
        A = sc.NextInt();
        B = sc.NextLong();
        N = sc.NextLong();

        // x = tB + B-1

        Console.WriteLine(Math.Min(N, B - 1) * A / B);
    }

    public static void Main(string[] args) => new Program().Solve();
}

namespace CompLib.Util
{
    using System;
    using System.Linq;

    class Scanner
    {
        private string[] _line;
        private int _index;
        private const char Separator = ' ';

        public Scanner()
        {
            _line = new string[0];
            _index = 0;
        }

        public string Next()
        {
            while (_index >= _line.Length)
            {
                _line = Console.ReadLine().Split(Separator);
                _index = 0;
            }

            return _line[_index++];
        }

        public int NextInt() => int.Parse(Next());
        public long NextLong() => long.Parse(Next());
        public double NextDouble() => double.Parse(Next());
        public decimal NextDecimal() => decimal.Parse(Next());
        public char NextChar() => Next()[0];
        public char[] NextCharArray() => Next().ToCharArray();

        public string[] Array()
        {
            _line = Console.ReadLine().Split(Separator);
            _index = _line.Length;
            return _line;
        }

        public int[] IntArray() => Array().Select(int.Parse).ToArray();
        public long[] LongArray() => Array().Select(long.Parse).ToArray();
        public double[] DoubleArray() => Array().Select(double.Parse).ToArray();
        public decimal[] DecimalArray() => Array().Select(decimal.Parse).ToArray();
    }
}


Measured memory_bytes: 27248
#include "bits/stdc++.h"
using namespace std;

int dx8[9] = { -1,-1,-1, 0, 1, 1, 1, 0 ,0};
int dy8[9] = { -1, 0, 1, 1, 1, 0,-1,-1,0 };
int main() {
	int H, W; cin >> H >> W;
	vector<vector<int>>field(H + 2, vector<int>(W + 2));
	for (int i = 0; i < H; ++i) {
		string st; cin >> st;
		for (int j = 0; j < W;++j){
			auto ch(st[j]);
			if (ch == '-') {

			}
			else if (ch == 'o') {
				for (int x = j; x < j + 3; ++x) {
					field[i + 1][x] = true;
				}
			}
			else {
				for (int way = 0; way < 9; ++way) {
					field[i + 1 + dy8[way]][j + 1 + dx8[way]] = true;
				}
			}

		}
	}
	int ans = 0;
	ans = accumulate(field.begin() + 2, field.end() - 1, 0, [](const int a, const vector<int>v){
		return accumulate(v.begin() + 1, v.end() - 1, 0) + a;
		
	});
	cout << (H-1)*W-ans << endl;
	return 0;
}

Measured memory_bytes: 3244
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;

int main() {
  map<string, P> mp;
  mp["N"] = {0, 1};
  mp["E"] = {1, 0};
  mp["S"] = {0, -1};
  mp["W"] = {-1, 0};

  int N;
  while (cin >> N, N) {
    auto tb = vector<vector<bool>>(21, vector<bool>(21, false));
    for (int i = 0; i < N; ++i) {
      int x, y; cin >> x >> y;
      tb[x][y] = true;
    }
    int x = 10;
    int y = 10;
    int M; cin >> M;
    for (int i = 0; i < M; ++i) {
      string d;
      int I;
      cin >> d >> I;
      int dx = mp[d].first;
      int dy = mp[d].second;
      for (int j = 0; j < I; ++j) {
        tb[x + dx][y + dy] = false;
        x += dx;
        y += dy;
      }
    }
    bool ans = true;
    for (int i = 0; i <= 20; ++i) {
      for (int j = 0; j <= 20; ++j) {
        if (tb[i][j]) ans = false;
      }
    }
    cout << ( (ans) ? "Yes" : "No" ) << endl;
  }
  return 0;
}



Measured memory_bytes: 3136
n=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
manzoku=0
for i in range(n-1):
  if A[i]+1==A[i+1]:
    manzoku+=C[A[i]-1]
manzoku+=sum(B)
print(manzoku)

Measured memory_bytes: 3064
#include <cstdlib>
#include <iostream>
#include <tuple>
#include <unordered_map>
#include <vector>
using namespace std;

constexpr int MAX_N = 10;
constexpr int MAX_M = 20;

typedef tuple<int, int, int> edge; // to, distance, index
#define to(e) get<0>(e)
#define dist(e) get<1>(e)
#define idx(e) get<2>(e)

int n, m;
vector<edge> E[MAX_N];
unordered_map<int, int> memo;

int dfs(int v, int used) {
	const int h = used * 10 + v;
	if(memo.count(h)) return memo.at(h);

	int &res = memo[h];
	for(const auto &e : E[v]) {
		if(used & (1 << idx(e))) continue;
		res = max(res, dfs(to(e), used | (1 << idx(e))) + dist(e));
	}
	return res;
}

void print_answer() {
	int ans = -1;
	int u = -1;
	
	for(int v = 0; v < n; ++v) {
		if(memo.count(v) && ans < memo.at(v)) {
			ans = memo.at(v);
			u = v;
		}
	}

	int rest = ans;
	int used = 0;
	vector<int> path;

	while(true) {
		path.emplace_back(u + 1);
		int next = n;
		int next_used = -1;
		int next_rest = -1;

		for(const auto &e : E[u]) {
			if(used & (1 << idx(e))) continue;

			const int v = to(e);
			const int n_used = used | (1 << idx(e));
			const int h = n_used * 10 + v;
			if(!memo.count(h) || memo.at(h) + dist(e) != rest) continue;

			if(next > v) {
				next = v;
				next_used = n_used;
				next_rest = memo.at(h);
			}
		}

		if(next == n) break;
		u = next;
		used = next_used;
		rest = next_rest;
	}

	cout << ans << endl;
	for(unsigned i = 0; i < path.size(); ++i) {
		cout << path[i] << (i + 1 == path.size() ? "\n" : " ");
	}
}

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

	while(cin >> n >> m && n) {
		for(int i = 0; i < n; ++i) {
			E[i].clear();
		}

		for(int i = 0; i < m; ++i) {
			int a, b, d;
			cin >> a >> b >> d;
			--a; --b;
			E[a].emplace_back(b, d, i);
			E[b].emplace_back(a, d, i);
		}

		memo.clear();
		for(int v = 0; v < n; ++v) {
			dfs(v, 0);
		}

		print_answer();
	}

	return EXIT_SUCCESS;;
}

Measured memory_bytes: 1292
#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;
//const int INF = 1<<29;
//const int MODINF = 1000000007;
using namespace std;

int main(){
    int N;
    cin >> N;
    if (N > 999) cout << "ABD";
    else cout << "ABC";
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long
const int N=1e5+5;
const int mod=1e9+7;
const double eps=1e-8;
const double PI = acos(-1.0);
#define lowbit(x) (x&(-x))
int main()
{
    std::ios::sync_with_stdio(false);
    char s[N];
    while(cin>>s)
    {
        int l=strlen(s),flag=0;
        for(int i=0; i<l; i++)
        {
            if(s[i]=='d')
            {
                if(i+6<l&&s[i+1]=='r'&&s[i+2]=='e'&&s[i+3]=='a'&&s[i+4]=='m'&&s[i+5]=='e'
                        &&s[i+6]=='r'&&s[i+7]!='a')
                {
                    i+=6;
                }
                else if(i+6<l&&s[i+1]=='r'&&s[i+2]=='e'&&s[i+3]=='a'&&s[i+4]=='m'&&s[i+5]=='e'
                        &&s[i+6]=='r'&&s[i+7]=='a')
                {
                    i+=4;
                }
                else if(i+4<l&&s[i+1]=='r'&&s[i+2]=='e'&&s[i+3]=='a'&&s[i+4]=='m')
                {
                    i+=4;
                }
                else
                {
                    flag=1;
                    break;
                }
            }
            else if(s[i]=='e')
            {
                if(i+5<l&&s[i+1]=='r'&&s[i+2]=='a'&&s[i+3]=='s'&&s[i+4]=='e'&&s[i+5]=='r')
                {
                    i+=5;
                }
                else if(i+4<l&&s[i+1]=='r'&&s[i+2]=='a'&&s[i+3]=='s'&&s[i+4]=='e')
                {
                    i+=4;
                }
                else
                {
                    flag=1;
                    break;
                }
            }
            else
            {
                flag=1;
                break;
            }
        }
        if(flag)
            cout<<"NO"<<endl;
        else
            cout<<"YES"<<endl;
    }
    return 0;
}

Measured memory_bytes: 384
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>

using namespace std;

using ll = long long;
using VI = vector<int>;
using PI = pair<int, int>;
using VII = vector<PI>;

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

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 (b<a) { a=b; return 1; } return 0; }

int gcd(int a,int b){return b?gcd(b,a%b):a;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

int main()
{
    int N;
    cin >> N;
    VII ans;
    rep(i, N)
    {
        int a;
        cin >> a;
        ans.emplace_back(make_pair(a, i+1));
    }
    sort(all(ans));
    rep(i, N)
    {
        printf("%d%c", ans[i].second, i == N-1 ? '\n' : ' ');
    }
    return 0;
}

Measured memory_bytes: 1780
// https://atcoder.jp/contests/abc078/tasks/abc078_a
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define REP(i, n) FOR(i, 0, n)
#define FOR(i, s, n) for (int i = (s), i##_len = (n); i < i##_len; ++i)
#define ALL(obj) (obj).begin(), (obj).end()
#define ALLR(obj) (obj).rbegin(), (obj).rend()

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    string x, y;
    cin >> x >> y;
    if (x < y) {
        cout << "<\n";
    } else if (x == y) {
        cout << "=\n";
    } else {
        cout << ">\n";
    }

    return 0;
}


Measured memory_bytes: 256
from random import random

K = 26
d = int(input())

c = list(map(int, input().split()))

s = []
for i in range(d):
    q = list(map(int, input().split()))
    s.append(q)

ans = []
last = [-1 for i in range(K)]
for i in range(d):
    x = []
    for j in range(K):
        x.append(pow(s[i][j] * s[i][j] * s[i][j] * c[j] * (i - last[j]) * c[j] * (i - last[j]), 2))

    sum = 0
    for j in range(K):
        sum += x[j]

    for k in range(K):
        x[j] /= sum

    prob = random()
    cur = 0
    for j in range(K):
        if cur + x[j] <= prob:
            cur += x[j]
            continue
        ans.append(j)
        last[j] = i
        break

def get_result():
    res = 0
    last = [-1 for i in range(K)]
    for i in range(d):
        res += s[i][ans[i]]
        last[ans[i]] = i
        for j in range(K):
            res -= c[j] * (i - last[j])
    return res

for u in ans:
    print(u + 1)

Measured memory_bytes: 9800
//https://atcoder.jp/contests/abc168/tasks/abc168_b
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll k;
	cin>>k;
	string x;
	cin>>x;
	ll n;
	n=x.length();
	if(k>=n)
	{
		cout<<x<<"\n";
	}
	else
	{
		ll i;
		for(i=0;i<k;i++)
		{
			cout<<x[i]<<"";
		}
		cout<<"..."<<"\n";
	}
	return 0;
}

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

using namespace std;

int main(){
  
  cout << fixed << setprecision(12);
  
  double a,b,C;

  cin >> a >> b >> C;

  double PI = acos(-1.0);

  C = C / 180 * PI;

  cout << a * b * sin(C) / 2 << endl;
  cout << a + b + sqrt(a*a+b*b-2*a*b*cos(C)) << endl;
  cout << b * sin(C) << endl;

  return 0;
}
  


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

int main(void){
	int n;
	cin >> n;
	double ans = 0, tmp;
	for(int i = 0; i < n; ++i){
		cin >> tmp;
		ans += 1.0 / tmp;
	}
	cout << 1.0 / ans << endl;
	return 0;
}

Measured memory_bytes: 256