akhauriyash/Code-Regression huggingface dataset:
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#include<map>
#include<bitset>
#include<set>
#include<assert.h>
#include<chrono>
#include<random>
#include<iostream>
#define LL long long
#define mp(x,y) make_pair(x,y)
#define pll pair<long long,long long>
#define pii pair<int,int>
#define SZ(x) ((int)x.size())
#define VI vector<int>
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
inline LL read()
{
	LL f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int stack[20];
template<typename T>inline void write(T x)
{
	if(x<0){putchar('-');x=-x;}
    if(!x){putchar('0');return;}
    int top=0;
    while(x)stack[++top]=x%10,x/=10;
    while(top)putchar(stack[top--]+'0');
}
template<typename T>inline void pr1(T x){write(x);putchar(' ');}
template<typename T>inline void pr2(T x){write(x);putchar('\n');}
template<typename T>inline void chkmin(T &x,T y){x=x<y?x:y;}
template<typename T>inline void chkmax(T &x,T y){x=x>y?x:y;}
const int MAXN=505;
const int dx[4]={0,-1,0,1};
const int dy[4]={-1,0,1,0};
int f[MAXN][MAXN],p[MAXN*MAXN],n;
int vis[MAXN][MAXN],tim;
bool a[MAXN][MAXN];
bool in(int x,int y){return x>=1&&x<=n&&y>=1&&y<=n;}
deque<pii> li;
void rollback(int x,int y)
{
	++tim;
	a[x][y]=0;li.push_front(mp(x,y));
	while(!li.empty())
	{
		pii T=li.front();li.pop_front();
		int u=T.first,v=T.second;
		if(vis[u][v]==tim)continue;vis[u][v]=tim;
		for(int k=0;k<4;k++)if(in(u+dx[k],v+dy[k]))
		{
			int p=u+dx[k],q=v+dy[k];
			if(f[p][q]>f[u][v]+a[u][v])
			{
				f[p][q]=f[u][v]+a[u][v];
				if(!a[u][v])li.push_front(mp(p,q));
				else li.push_back(mp(p,q));
			}
		}
	}
}
int main()
{
	#ifdef Rose
		double BeginJudgeTime=clock();
	#endif
	memset(a,true,sizeof(a));
	n=read();LL ans=0;
	for(int i=1;i<=n*n;i++)p[i]=read();
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)
	{
		f[i][j]=i-1;chkmin(f[i][j],n-i);chkmin(f[i][j],j-1);chkmin(f[i][j],n-j);
	}
	for(int i=1;i<=n*n;i++)
	{
		int x=(p[i]-1)/n+1,y=(p[i]-1)%n+1;
		ans+=f[x][y];
		rollback(x,y);
	}
	pr2(ans);
	#ifdef Rose
		double EndJudgeTime=clock();
		cerr<<"JudgeTime is"<<" ";
		cerr<<(EndJudgeTime-BeginJudgeTime)/CLOCKS_PER_SEC<<endl;
	#endif
	return 0;
}


Measured memory_bytes: 7664
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        int k = Integer.parseInt(sc.next());
        int[] p = new int[n];
        for(int i=0; i<n; i++) {
            p[i] = Integer.parseInt(sc.next());
        }
        
        Arrays.sort(p);
        
        int sum = 0;
        for(int i=0; i<k; i++) {
            sum += p[i];
        }
        
        System.out.println(sum);
    }
}


Measured memory_bytes: 37560
K,N = map(int, input().split())
A = list(map(int, input().split()))
sub = []

for i in range(N-1):
    sub.append(A[i+1]-A[i])

a = K-A[N-1]

sub.append(a+A[0])
ans = K - max(sub)

print(ans)

Measured memory_bytes: 25452
while True:
    h,w = map(int,input().split())
    if h == w == 0:
        break
    for y in range(h):
        for x in range(w):
            if (y+x)%2 == 0:
                print('#',end="")
            if (y+x)%2 == 1:
                print('.',end="")
        print()
    print()

Measured memory_bytes: 6804
import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n, t;
        double a = 0.0, x, h;

        n = sc.nextInt();
        t = sc.nextInt();
        for(int i = 0; i < n; i++) {
            x = sc.nextInt();
            h = sc.nextInt();
            a = Math.max(a, h / x);
        }

        System.out.printf("%.6f", a * t);
    }
}

Measured memory_bytes: 34052
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)n; i++)
#define REPvec(itr, mp) for (auto itr = mp.begin(); itr != mp.end(); itr++)
#define all(x) x.begin(), x.end()
#define MOD 1000000007  // 1e9+7
using namespace std;
typedef long long int ll;
typedef vector<int> vecint;
typedef vector<ll> vecll;
typedef vector<string> vecstr;
typedef vector<bool> vecbool;
typedef vector<vector<int>> vec2int;
typedef pair<int, int> P;
////////////////////////////////////////////////
void init() {
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(15);
}
////////////////////////////////////////////////
int main() {
  init();
  string n;
  cin >> n;
  if (n == "ABC") {
    cout << "ARC" << endl;
  } else {
    cout << "ABC" << endl;
  }
}

Measured memory_bytes: 3616
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const lint mod = 1e9 + 7;
#define all(x) (x).begin(), (x).end()
#define bitcount(n) __builtin_popcountl((lint)(n))
#define fcout cout << fixed << setprecision(15)
#define highest(x) (63 - __builtin_clzl(x))
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; }
template<class T = string, class U = char>int character_count(T text, U character){ int ans = 0; for(U i: text){ ans += (i == character); } return ans; }
lint power(lint base, lint exponent, lint module){ if(exponent % 2){ return power(base, exponent - 1, module) * base % module; }else if(exponent){ lint root_ans = power(base, exponent / 2, module); return root_ans * root_ans % module; }else{ return 1; }}
struct position{ int y, x; }; position mv[4] = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}}; // double euclidean(position first, position second){ return sqrt((second.x - first.x) * (second.x - first.x) + (second.y - first.y) * (second.y - first.y)); }
template<class T, class U> string to_string(pair<T, U> x){ return to_string(x.first) + "," + to_string(x.second); } string to_string(string x){ return x; }
template<class itr> void array_output(itr start, itr goal){ string ans; for(auto i = start; i != goal; i++) ans += to_string(*i) + " "; if(!ans.empty()) ans.pop_back(); cout << ans << endl; }
template<class itr> void cins(itr first, itr last){ for(auto i = first; i != last; i++){ cin >> (*i); } }
template<class T> T gcd(T a, T b){ if(a && b){ return gcd(min(a, b), max(a, b) % min(a, b)); }else{ return a; }} template<class T> T lcm(T a, T b){ return a / gcd(a, b) * b; }
struct combination{ vector<lint> fact, inv; combination(int sz) : fact(sz + 1), inv(sz + 1){ fact[0] = 1; for(int i = 1; i <= sz; i++){ fact[i] = fact[i - 1] * i % mod; } inv[sz] = power(fact[sz], mod - 2, mod); for(int i = sz - 1; i >= 0; i--){ inv[i] = inv[i + 1] * (i + 1) % mod; } } lint C(int p, int q) const{ if(q < 0 || p < q) return 0; return (fact[p] * inv[q] % mod * inv[p - q] % mod); } };
template<class itr> bool next_sequence(itr first, itr last, int max_bound){ itr now = last; while(now != first){ now--; (*now)++; if((*now) == max_bound){ (*now) = 0; }else{ return true; } } return false; }

combination table(1e6);

lint P(int p, int q){
    if(q < 0 || p < q) return 0;
    return (table.fact[p] * table.inv[p - q] % mod);
}

int main(){
    int N, K;
    cin >> N >> K;
    if(N == 1){
        cout << K << endl;
        return 0;
    }
    vector<int> roads[N];
    for(int i = 0; i < N - 1; i++){
        int a, b;
        cin >> a >> b;
        a--, b--;
        roads[a].push_back(b);
        roads[b].push_back(a);
    }
    lint ans = 1;
    for(auto i: roads){
        ans = (ans * P(K - 2, int(i.size()) - 1)) % mod;
    }
    cout << ans * (K - 1) % mod * K % mod << endl;
}

Measured memory_bytes: 22136
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const  ll INF = 1e18;
const  ll MOD = 1e9 + 7;
#define all(v) v.begin(), v.end()
#define repi(i,n,init) for(ll i=init;i<(n);i++)
#define repd(i,n,init) for(ll i=(n);i>=init;i--)
#define repm(i,m) for(auto i=m.begin();i!=m.end();i++)

int main()
{
    ll N;
    cin >> N;
    cout << N*800 - ll(N/15)*200 << endl;
    return 0;
}

Measured memory_bytes: 256
package main

// ARC062C - AtCoDeerくんと選挙速報
// https://atcoder.jp/contests/arc062/tasks/arc062_a

import "fmt"

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func ceil(n, m int) int {
	return (n + m - 1) / m
}

func main() {
	var N int
	fmt.Scan(&N)
	T, A := 1, 1
	for i := 0; i < N; i++ {
		var t, a int
		fmt.Scan(&t, &a)
		n := max(ceil(T, t), ceil(A, a))
		T = n * t
		A = n * a
	}
	fmt.Println(T + A)
}


Measured memory_bytes: 512
#include<stdio.h>
#define N 8
#define free -1
#define notfree 1
#define FALSE 2
#define TRUE 3

 int row[N],col[N],dpos[2*N-1],dneg[2*N-1];
 int X[N][N];

 void initialize(void);
 void printbord(void);
 void recursive(int);

 int main(){
            int i,j,k,r,c;
            initialize();
            
            for(i=0;i<N;i++){
                             for(j=0;j<N;j++){
                                              X[i][j]=FALSE;
                                              }
                             }
            scanf("%d",&k);
            for(i=0;i<k;i++){
                             scanf("%d%d",&r,&c);
                             X[r][c]=TRUE;
                             }
            recursive(0);

            return 0;
            }


 void initialize(){
                   int i;
                   for(i=0;i<N;i++){
                                    row[i]=free;
                                    col[i]=free;
                                    }

                   for(i=0;i<2*N-1;i++){
                                        dpos[i]=free;
                                        dneg[i]=free;
                                        }
                    }

 void printboard(){
                   int i,j;
                   for(i=0;i<N;i++){
                         for(j=0;j<N;j++){
                                    if(X[i][j]==TRUE){
                                                      if(row[i]!=j)return;
                                                      }
                                          }
                                    }

                   for(i=0;i<N;i++){
                                    for(j=0;j<N;j++){
                                                     if(row[i]==j)printf("Q");
                                                     else printf(".");
                                                     }
                                    printf("\n");
                                    }
                   }

 void recursive(int i){
                    int j;
                    if(i==N){
                             printboard();
                             return;
                             }
                    for(j=0;j<N;j++){
                      if(notfree==col[j]||notfree==dpos[i+j]||notfree==dneg[i-j+N-1])continue;
                      row[i]=j;
                      col[j]=dpos[i+j]=dneg[i-j+N-1]=notfree;
                      recursive(i+1);
                      row[i]=col[j]=dpos[i+j]=dneg[i-j+N-1]=free;
                      }
                     }





Measured memory_bytes: 2116
#include<iostream>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<set>
#include<queue>
using namespace std;

typedef long long ll;

typedef struct {
  int x,y;
}Points;

bool comp1(const Points&l, const Points&r) { return l.x < r.x; };
bool comp2(const Points&l, const Points&r) { return l.y > r.y; };
bool f1[110];
bool f2[110];

int main() {
  int N; cin >> N;
  vector<Points> red(N);
  vector<Points> blue(N);
  for ( int i = 0; i < N; i++ ) cin >> red[i].x >> red[i].y;
  for ( int i = 0; i < N; i++ ) cin >> blue[i].x >> blue[i].y;

  sort(red.begin(),red.end(),comp2);
  sort(blue.begin(),blue.end(),comp1);  
  int cnt1 = 0;
  // cout << endl;
  for ( int i = 0; i < N; i++ ) {
    // cout << red[i].x << " " << red[i].y << endl;
  }
    for ( int i = 0; i < N; i++ ) {
      for ( int j = 0; j <  N; j++ ) {

	if( red[j].x < blue[i].x && red[j].y < blue[i].y
	    && f1[i]== false && f2[j] == false ) {
	  f1[i] = true;
	  f2[j] = true;
	  //	cout <<  blue[i].x << " " << blue[i].y << " " << 
	  //  red[j].x << " " <<  red[j].y <<  endl;		  
	  //  cout << "f1[i]" << " " <<i << " " <<  f1[i] << endl;

	  cnt1++;
	}
      }
    }

/*
  sort(red.begin(),red.end(),comp2);
  sort(blue.begin(),blue.end(),comp2);

  int cnt2 = 0;
  for ( int i = 0; i < N; i++ ) {
    for ( int j = 0; j <  N; j++ ) {
      if( red[i].x < blue[i].x && red[j].y < blue[j].y
	  && f2[i] == false ) {
	f2[i] = true;
	cnt2++;
      }
    }
  }  
*/		
//  cout << max(cnt1,cnt2) << endl;
cout << cnt1 << endl;
  return 0;
}


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

#define _sel(_1, _2, x, ...) x
#define repn(i, n) for (ll i = 0; i < (n); i++)
#define reps(i, a, b) for (ll i = (a); i < (b); i++)
#define rep(i, ...) _sel(__VA_ARGS__, reps, repn)(i, __VA_ARGS__)
#define reppn(i, n) for (ll i = 1; i <= (n); i++)
#define repps(i, a, b) for (ll i = (a); i <= (b); i++)
#define repp(i, ...) _sel(__VA_ARGS__, repps, reppn)(i, __VA_ARGS__)
#define rrepn(i, n) for (ll i = (n) - 1; i >= 0; i--)
#define rreps(i, a, b) for (ll i = (b) - 1; i >= (a); i--)
#define rrep(i, ...) _sel(__VA_ARGS__, rreps, rrepn)(i, __VA_ARGS__)
#define rreppn(i, n) for (ll i = (n); i >= 1; i--)
#define rrepps(i, a, b) for (ll i = (b); i >= (a); i--)
#define rrepp(i, ...) _sel(__VA_ARGS__, rrepps, rreppn)(i, __VA_ARGS__)

#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define rng(v) (v).begin(), (v).end()
#define rrng(v) (v).rbegin(), (v).rend()
#define _shv(v) for (auto _t1 : v) cerr << _t1 << " "; cerr << endl;
#define dg(x) cerr << #x << ": " << (x) << endl;
#define dgv(v) cerr << #v << ": "; _shv(v);
#define dgm(m) cerr << #m << ":" << endl; for (auto _t2 : m) { _shv(_t2); }

using namespace std;
using ll = long long int;
using ld = long double;
using pii = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
using vb = vector<bool>;
using vc = vector<char>;
using vs = vector<string>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;
using vvb = vector<vector<bool>>;
using vvc = vector<vector<char>>;
using vvs = vector<vector<string>>;

const int INF = 1e9;
const ll LINF = 1e18;
const ll MOD = 1e9 + 7;
const int DX[4] = {1, 0, -1, 0};
const int DY[4] = {0, 1, 0, -1};

template<typename T> inline void pt(T x) { cout << x << endl; }
template<typename T> inline void inv(T& v) { for (auto& t : v) cin >> t; }
template<typename T> inline int siz(T& x) { return x.size(); }
template<typename T> inline ll pow2(T n) { return 1ll << n; }
template<typename T, typename U> inline int bit(T x, U n) { return x >> n & 1; }
template<typename T, typename U>
inline bool umax(T& m, U x) { if (m < x) { m = x; return true; } return false; }
template<typename T, typename U>
inline bool umin(T& m, U x) { if (m > x) { m = x; return true; } return false; }


int main() {
    string s, t;
    cin >> s >> t;

    vvi dp(siz(s) + 1, vi(siz(t) + 1, 0));
    rep(i, siz(s)) {
        rep(j, siz(t)) {
            if (s[i] == t[j]) {
                dp[i + 1][j + 1] = dp[i][j] + 1;
            } else {
                if (dp[i + 1][j] > dp[i][j + 1])
                    dp[i + 1][j + 1] = dp[i + 1][j];
                else
                    dp[i + 1][j + 1] = dp[i][j + 1];
            }
        }
    }

    string ans = "";
    int i = siz(s), j = siz(t);
    while (i && j) {
        if (s[i - 1] == t[j - 1]) {
            ans.pb(s[i - 1]);
            i--;
            j--;
        } else {
            if (dp[i][j - 1] > dp[i - 1][j]) {
                j--;
            } else {
                i--;
            }
        }
    }
    reverse(rng(ans));
    pt(ans);

    return 0;
}


Measured memory_bytes: 35584
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)n;i++)
typedef long long ll;
int main(void){
    int n;cin>>n;
    vector<vector<int>> a(n,vector<int>(n-1));
    rep(i,n){
        rep(j,n-1){
            cin>>a[i][j];
            a[i][j]--;
        }
    }
    vector<int> now(n,0);//今i人目の人は何回戦ったか
    int fin=0;//n-1回戦った人の数
    int res=1;//fin=nになるまでに何日かかったか
    queue<int> que;
    rep(i,n) que.push(i);
    while(que.size()>0){
        vector<bool> fight(n,true);
        bool match=false;//1戦もできなかった場合-1を返すフラグ
        queue<int> que2;
        while(que.size()){
            int i=que.front();
            que.pop();
            if(now[i]==n-1) continue;
            int op=a[i][now[i]];
            if(a[op][now[op]]==i&&fight[op]&&fight[i]){
                match=true;
                now[i]++;
                now[op]++;
                if(now[i]==n-1)fin++;
                if(now[op]==n-1)fin++;
                fight[i]=false;
                fight[op]=false;
                que2.push(op);
                que2.push(i);
            }
        }
        swap(que,que2);
        if(!match){
            cout<<-1<<endl;
            return 0;
        }else if(fin==n){
            cout<<res<<endl;
            return 0;
        }
        res++;
    }
    return 0;
}

Measured memory_bytes: 4224
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef long double ld;
const int inf=1e9+7;
const ll longinf=1LL<<60;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define F first
#define S second

const int mx=200010;
const ll mod=1e9+7;


int main(){
  double a,b; cin >> a >> b;
  
  cout << fixed << setprecision(10) << a/b << endl;    
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <stdio.h>
#include <set>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>
#include <memory.h>
#include <string>
#include <sstream>
#include <cstdlib>
#include <ctime>
#include <cassert>

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;

#define MP make_pair
#define PB push_back
#define FF first
#define SS second

#define FORN(i, n) for (int i = 0; i <  (int)(n); i++)
#define FOR1(i, n) for (int i = 1; i <= (int)(n); i++)
#define FORD(i, n) for (int i = (int)(n) - 1; i >= 0; i--)

#define DEBUG(X) { cout << #X << " = " << (X) << endl; }
#define PR0(A,n) { cout << #A << " = "; FORN(_,n) cout << A[_] << ' '; cout << endl; }

#define MOD 1000000007
#define INF 2000000000

int GLL(LL& x) {
    return scanf("%lld", &x);
}

int GI(int& x) {
    return scanf("%d", &x);
}

int n, a, b;

int main() {
    GI(n); GI(a); GI(b);

    int res = 0;

    FORN(i, n) {
        int t; GI(t);
        if (t < a || t >= b) res++;
    }

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

Measured memory_bytes: 384
#include <queue>
#include <algorithm>
#include <vector>
#include <iostream>
#include <atcoder/convolution>
using namespace std;

constexpr int M = 998244353;

class ModComb {
    long long *fact, *facti;
    const int mod;
public:
    explicit ModComb(int n, int m) : mod(m) {
        fact = new long long[n+1];
        facti = new long long[n+1];
        fact[0] = 1; facti[0] = 1;
        for (int i = 1; i <= n; i++) fact[i] = (fact[i-1] * i) % m;
        // calc 1/n!
        long long &inv = facti[n], pw = fact[n];
        inv = 1;
        for (int e = mod-2; e > 0; e /= 2) {
            if (e&1) inv = inv * pw % mod;
            pw = pw * pw % mod;
        }
        for (int i = n-1; i > 0; i--) facti[i] = (facti[i+1] * (i+1)) % m;
    }

    ~ModComb() {
        if (fact) delete[] fact;
        if (facti) delete[] facti;
    }

    long long getFact(int n) const {
        return fact[n];
    }

    long long getFactInv(int n) const {
        return facti[n];
    }

    long long getComb(int n, int k) const {
        if (n < 0 || k < 0 || k > n) return 0;
        return fact[n] * facti[k] % mod * facti[n-k] % mod;
    }

    long long getPerm(int n, int k) const {
        if (n < 0 || k < 0 || k > n) return 0;
        return fact[n] * facti[n-k] % mod;
    }
};

int main() {
    int n; cin >> n;
    ModComb mc(2*n, M);
    vector<int> c(100100, 0);
    for (int i = 0; i < 2*n; i++) {
        int h; cin >> h;
        c[h]++;
    }
    vector<int> f;
    for (int a : c) if (a > 1) f.push_back(a);
    sort(f.begin(), f.end());
    long long df[2*n+1];
    for (int i = 0; i <= 2*n; i++)
        df[i] = i < 2 ? 1 : df[i-2] * i % M;

    priority_queue<pair<int, vector<int> > > pq;
    pq.push({0, {1}});
    for (int a : f) {
        vector<int> v;
        v.push_back(1);
        for (int j = 1; 2*j <= a; j++)
            v.push_back(mc.getComb(a, 2*j) * df[2*j-1] % M);
        pq.push({-v.size(), move(v)});
    }
    while (pq.size() > 1) {
        vector<int> v = move(pq.top().second);
        pq.pop();
        vector<int> w = move(pq.top().second);
        pq.pop();
        vector<int> u = atcoder::convolution(v, w);
        pq.push({-u.size(), u});
    }
    vector<int> H = pq.top().second;
    long long ans = 0;
    for (int k = 0; k < H.size(); k++) {
        ans += (k % 2 ? -1 : 1) * (k == n ? 1 : df[2*(n-k)-1]) * H[k] % M;
    }
    cout << (ans % M + M) % M << endl;
}


Measured memory_bytes: 7840
#include <iostream>
#include <algorithm>
#define INF 1000000013
using namespace std;
typedef long long ll;
ll dp[110][100010];

int main(){
  ll n,w;
  cin >> n >> w;
  ll a[n],b[n];
  for(ll i=0;i<n;i++) cin >> a[i] >> b[i];
  for(ll i=0;i<n;i++){
    for(ll j=0;j<=w;j++){
      if(j>=a[i]) dp[i+1][j]=max(dp[i][j-a[i]]+b[i],dp[i][j]);
      else dp[i+1][j]=dp[i][j];
    }
  }
  cout << dp[n][w] << endl;
}

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

#define rep(i,x,y) for(int i=(x);i<(y);++i)
#define debug(x) #x << "=" << (x)

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define print(x)
#endif

const int inf=1e9;
const int64_t inf64=1e18;
const double eps=1e-9;

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
    os << "[";
    for (const auto &v : vec) {
    	os << v << ",";
    }
    os << "]";
    return os;
}

pair<int,int> farthest_vertex(const vector<vector<pair<int,int>>> &graph,int v,int p){
    pair<int,int> res(v,0); //(最も遠い頂点,距離)
    for(auto &e:graph[v]){
        if(e.first==p) continue;

        auto tmp=farthest_vertex(graph,e.first,v);
        tmp.second+=e.second;
        if(res.second<tmp.second) res=tmp;
    }
    return res;
}


void solve(){
    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> count1(n+1),count2(n+1);
    rep(i,0,n){
        cin >> a[i];
        ++count2[a[i]];
    }
    sort(a.rbegin(),a.rend());

    vector<vector<pair<int,int>>> graph(a[0]+1);
    rep(i,0,a[0]){
        graph[i].push_back(make_pair(i+1,1));
        graph[i+1].push_back(make_pair(i,1));
    }

    rep(i,0,graph.size()){
        auto p=farthest_vertex(graph,i,-1);
        ++count1[p.second];
    }

    rep(i,0,n+1){
        if(count1[i]>count2[i]){
            cout << "Impossible" << endl;
            return;
        }
        while(count1[i]<count2[i]){
            bool f=false;
            rep(j,0,graph.size()){
                auto p=farthest_vertex(graph,j,-1);
                if(p.second==i-1){
                    int s=graph.size();
                    graph.push_back(vector<pair<int,int>>());
                    graph[j].push_back(make_pair(s,1));
                    graph[s].push_back(make_pair(j,1));
                    ++count1[i];
                    f=true;
                    break;
                }
            }
            if(!f){
                cout << "Impossible" << endl;
                return;
            }
        }
    }
    cout << "Possible" << endl;
}

int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(10);
    solve();
    return 0;
}


Measured memory_bytes: 256
// Ver19.03
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define INF (1 << 29) * 2
#define LLINF 4545454545454545454
#define MOD 1000000007
#define ll long long
#define ull unsigned long long
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))
int upll(const void *a, const void *b) { return *(ll *)a < *(ll *)b ? -1 : *(ll *)a > *(ll *)b ? 1 : 0; }
int downll(const void *a, const void *b) { return *(ll *)a < *(ll *)b ? 1 : *(ll *)a > *(ll *)b ? -1 : 0; }
void sortup(ll *a, int n) { qsort(a, n, sizeof(ll), upll); }
void sortdown(ll *a, int n) { qsort(a, n, sizeof(ll), downll); }

ll a[110];
ll n, b, cnt, ans = LLINF;
int main()
{
  scanf("%lld", &n);
  for (int i = 0; i < n; i++)
  {
    scanf("%lld", a + i);
    b += a[i];
  }
  for (int i = 0; i < n; i++)
  {
    cnt += a[i];
    ans = MIN(llabs(cnt - (b - cnt)), ans);
  }
  printf("%lld\n", ans);
  return 0;
}


Measured memory_bytes: 128
x,y,s,t = map(float, input().split())
a = int(input())
s-=x
t-=y
while a:
    a -= 1
    p,q = map(float, input().split())
    p-=x
    q-=y
    ans_x = s*(q*t+p*s)/(t*t+s*s)
    ans_y = t*(q*t+p*s)/(t*t+s*s)
    print(x+ans_x, y+ans_y)



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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<long long, int> ll_i;

#define PI 3.141592653589793238462643383279
#define mod 1000000007LL
#define rep(i, n) for(i = 0;i < n;++i)
#define rep1(i, n) for(i = 1;i < n;++i)
#define per(i, n) for(i = n - 1;i > -1;--i)
#define int(x) int x; scanf("%d",&x)
#define int2(x, y) int x, y; scanf("%d%d",&x, &y)
#define int3(x, y, z) int x, y, z; scanf("%d%d%d",&x, &y, &z)
#define int4(v, x, y, z) int v, x, y, z; scanf("%d%d%d%d", &v, &x, &y, &z)
#define int5(v, w, x, y, z) int v, w, x, y, z; scanf("%d%d%d%d%d", &v, &w, &x, &y, &z)
#define pri(x) cout << (x) << "\n"
#define pri2(x, y) cout << (x) << " " << (y) << "\n"
#define pri3(x, y, z) cout << (x) << " " << (y) << " " << (z) << "\n"
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(),(a).end()
#define kabe puts("---------------------------")
#define kara puts("")
#define debug(x) cout << " --- " << (x) << "\n"
#define debug2(x, y) cout << " --- " << (x) << " " << (y) << "\n"
#define debug3(x, y, z) cout << " --- " << (x) << " " << (y) << " " << (z) << "\n"
#define X first
#define Y second
#define eps 0.0001
#define prid(x) printf("%.15lf\n", x)

int t[26] = {0};
int cnt[26] = {0};

signed main(void){
  int i, j;
  for(int testcase = 0;testcase >= 0;testcase++){
    int(n);
    rep(i, 26)t[i] = 100;

    string s;
    rep(i, n){
      cin >> s;
      rep(j, 26)cnt[j] = 0;
      rep(j, s.size())++cnt[s[j] - 'a'];
      rep(j, 26)t[j] = min(cnt[j], t[j]);
    }
    rep(i, 26)rep(j, t[i])printf("%c", 'a' + i);
    puts("");

/*/

//*/ break;
  }
  return 0;
}


Measured memory_bytes: 256
# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <stack>
# include <queue>
# include <list>
using namespace std;
using LL = long long;
constexpr int MOD = 1000000000 + 7;
constexpr int INF = 2000000000;
const double PI = acos(-1);

int main() {
	priority_queue<int>pq;
	string s;
	int n;
	while (cin >> s&&s != "end") {
		if (s == "insert") {
			cin >> n;
			pq.push(n);
		}
		else {
			cout << pq.top() << endl;
			pq.pop();
		}
	}
}

Measured memory_bytes: 7016
#include <stdio.h>
#include <string.h>
int main()
{
  char s[100];
int i;
  for(i=0;i<3;i++){
    scanf("%c",&s[i]);
  }

  if(s[1]=='B'){
    printf("ARC");
  }
  else if(s[1]=='R'){
    printf("ABC");
  }
return 0;
}


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

static const int MAX = 200000;

int main() {
    int R[MAX], n;

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

    int maxv = - 2000000000;
    int minv = R[0];

    for (int i = 1; i < n; i++){
        maxv = max(maxv, R[i] - minv);
        minv = min(minv, R[i]);
    }

    cout << maxv << endl;

    return 0;
}

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

//template
#define rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define ALL(v) (v).begin(),(v).end()
typedef long long int ll;
const int inf = 0x3fffffff; const ll INF = 0x1fffffffffffffff; const double eps=1e-12;
template<typename T>inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<typename T>inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
//end

int n,a[201010],par[201010]; vector<int> g[501010];
bool check(int v,int x){ //cycle
   a[v]=x; int cur=par[v];
   while(v!=cur){
      set<int> st;
      for(int nxt:g[cur])st.insert(a[nxt]);
      a[cur]=0;
      while(st.count(a[cur]))a[cur]++;
      cur=par[cur];
   }
   int t=0; set<int> st;
   for(int nxt:g[v])st.insert(a[nxt]);
   while(st.count(t))t++;
   return t==x;
}

int main(){
   int n; cin>>n;
   rep(i,0,n){
      cin>>par[i]; par[i]--;
      g[par[i]].push_back(i);
   }
   queue<int> que;
   rep(i,0,n){
      if(g[i].size()==0)que.push(i);
      else a[i]=-1;
   }
   while(que.size()){
      int v=que.front(); que.pop();
      set<int> st;
      bool f=0;
      for(int nxt:g[v]){
         if(a[nxt]<0){
            f=1; break;
         }
         st.insert(a[nxt]);
      }
      if(f)continue;
      a[v]=0;
      while(st.count(a[v]))a[v]++;
      que.push(par[v]);
   }
   int v=-1; set<int> st;
   rep(i,0,n)if(a[i]==-1){
      v=i; break;
   }
   for(int nxt:g[v])if(a[nxt]!=-1)st.insert(a[nxt]);
   int x=0;
   while(st.count(x))x++;
   if(check(v,x)){
      puts("POSSIBLE");
      return 0;
   }
   x++;
   while(st.count(x))x++;
   if(check(v,x)){
      puts("POSSIBLE");
      return 0;
   }
   puts("IMPOSSIBLE");
   return 0;
}

Measured memory_bytes: 22164
#include <iostream>
#include <stdio.h>

using namespace std;
typedef long long int lint;

void answer()
{
	int a, b;
	cin >> a >> b;
	printf("%d %d %lf\n", a / b, a % b, (double)a / b);
}

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

Measured memory_bytes: 1188
program main
      implicit none
      integer :: x
      integer :: i, j
      logical :: flag

      read *, x
      do i = x, 100003
        flag = .true.
        do j = 2, int(sqrt(real(x)+1))
          if ( mod(i,j) == 0 ) then
            flag = .false.
            exit
          end if
        end do
        if ( flag ) then
          print *, i
          stop
        end if
      end do

end program main

      


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

int main() {
  int n;
  cin >> n;
  array<int, 3> a;
  for (auto &e : a) cin >> e;
  vector<string> s(n);
  for (auto &e : s) cin >> e;

  for (auto &e : a) e = min(e, 2);

  vector<char> r, t;
  vector<vector<vector<bool>>> v(n, vector<vector<bool>>(7, vector<bool>(7)));
  auto dfs = [&](auto &&dfs, int i) {
    if (i == n) {
      r = t;
      return;
    }
    if (v[i][a[0]][a[1]]) return;
    v[i][a[0]][a[1]] = true;
    for (int k = 0; k < 2; k++) {
      int x = s[i][k] - 'A';
      int y = s[i][1 - k] - 'A';
      if (a[x] <= 0) continue;
      a[x]--;
      a[y]++;
      t.push_back('A' + y);
      dfs(dfs, i + 1);
      t.pop_back();
      a[x]++;
      a[y]--;
    }
  };
  dfs(dfs, 0);

  if (r.empty()) {
    cout << "No" << endl;
  } else {
    cout << "Yes" << endl;
    for (auto e : r) cout << e << endl;
  }
}


Measured memory_bytes: 68460
#include <stdio.h>
#include <string.h>
int main(){
    char s[1002];
    int x, n;
    scanf("%s", s);
    while(s[0]!='0'){
        x=0;
        n=strlen(s);
        for(int i=0; i<n; i++){
            x+=s[i]-48;
        }
        printf("%d\n", x);
        scanf("%s", s);
    }
}


Measured memory_bytes: 2088
#include <bits/stdc++.h>
using namespace std;
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
long long int mod = 1000000007;
long long fast_exp(long long a,long long n,long long mod1)
    {
     
      if (n==0)return 1;
      else if (n==1)return a;
      if (n%2==0)return fast_exp((a*a)%mod1,n/2,mod1);
      else return (a*fast_exp((a*a)%mod1,n/2,mod1))%mod1;
    }
static bool is_power[1000001]={false};
void sieve()
{
    for (long long int c=2;c<=1000000;c++)
        if (is_power[c]==true)
            continue;
        else 
            for (long long int c1=c*c;c1<=1000000;c1=c1*c)
                is_power[c1]=true;
    return ;
}
   int gcd(int a,int b)
    {
        if (b<a)return gcd(b,a);
        else if (b%a==0)return a;
        else return gcd(b%a,a);
     
    }
int main()
{
    
    fast_io;
    int t;
    t=1;//cin >> t;
    for (;t>0;t--)
    {
       int n;
       cin >> n;
       string a;
       cin >> a;
       int cols[4001][3]={0};
       for (int c=1;c<=a.size();c++)
        if (a[c-1]=='R')
            cols[c][0]=cols[c-1][0]+1,cols[c][1]=cols[c-1][1],cols[c][2]=cols[c-1][2];
        else if (a[c-1]=='G')
            cols[c][1]=cols[c-1][1]+1,cols[c][2]=cols[c-1][2],cols[c][0]=cols[c-1][0];
        else if (a[c-1]=='B')
            cols[c][2]=cols[c-1][2]+1,cols[c][1]=cols[c-1][1],cols[c][0]=cols[c-1][0]; 
       
long long res=0;
       for (int c=0;c<a.size();c++)
        for (int c1=c+2;c1<a.size();c1++)
            if (a[c]==a[c1])
                continue;
            else {
                    if (a[c]!='R'&&a[c1]!='R')
                        res+=cols[c1+1][0]-cols[c+1][0]-((c+c1)%2!=0?0:(a[(c+c1)/2]=='R')?1:0);
                    else if (a[c]!='G'&&a[c1]!='G')
                        res+=cols[c1+1][1]-cols[c+1][1]-((c+c1)%2!=0?0:(a[(c+c1)/2]=='G')?1:0);
                    else if  (a[c]!='B'&&a[c1]!='B')
                        res+=cols[c1+1][2]-cols[c+1][2]-((c+c1)%2!=0?0:(a[(c+c1)/2]=='B')?1:0);
                
                
            }
            cout << res << endl;



    }
    return 0;
}




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

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


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

int main(){
  int N, K;
  cin >> N >> K;
  vector<int> A(N);
  rep(i, N){
    cin >> A[i];
  }
  sort(A.begin(), A.end(), greater<int>());
  int sum = 0;
  rep(i, K){
    sum += A[i];
  }
  
  cout << sum << endl;
}


Measured memory_bytes: 256
N = int(input())
lis = []
for _ in range(N):
  X = list(map(int,input().split()))
  X.reverse()
  lis.append(X)
lis.sort()
t = 0
for i in range(N):
  t += lis[i][1]
  if t > lis[i][0]:
    print("No")
    exit()
print("Yes")

Measured memory_bytes: 51288
import itertools

N = input()
seq = ('3', '5', '7')
cnt = 0

for i in range(1, len(N)+1):
    for j in itertools.product(seq, repeat=i):
        if int(''.join(j)) > int(N):
            break
        if '3' not in j or '5' not in j or '7' not in j:
            continue
        if int(''.join(j)) < 357:
            continue
        cnt += 1

print(cnt)

Measured memory_bytes: 3060
#include <string>
#include <iostream>
#include <stack>
#include <queue> // priority_queue も入ってる
#include <set>   // 要素数は size() で取得 multisetもある
#include <map>
#include <array> // sizeはコンパイル時定数で固定
#include <vector>
#include <numeric>   // accumulate, gcd
#include <algorithm> // count_ifに必要
#include <iomanip>   // cout << setprecision(15) << x で小数の出力精度を指定
#include <tuple>
#include <utility> //pair
#include <cmath>

using namespace std;
// 問題が起こるまでintは使用禁止2020-04-13
using ll = long long;

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

template <class InputIterator, class T>
bool contains_itr(InputIterator iterator, const T &value)
{
    if (find(iterator.begin(), iterator.end(), value) == iterator.end())
        return false;
    else
        return true;
}

template <class T>
bool contains_set(set<T> st, const T &value)
{
    if (st.find(value) == st.end())
    {
        return false;
    }
    else
    {
        return true;
    }
}

template <class InputIterator>
auto sum(InputIterator iterator)
{
    return accumulate(iterator.begin(), iterator.end(), 0);
}

// endは排他的(exclusive)なので注意
vector<ll> range(ll begin, ll end)
{
    vector<ll> result;
    for (ll i = begin; i < end; ++i)
    {
        result.push_back(i);
    }
    return result;
}

// =========ここまでテンプレ============

int main()
{
    ll n;
    cin >> n;
    string alphabets = "abcdefghijklmnopqrstuvwxyz";
    string result;
    while (true)
    {
        --n;
        ll q = n / 26;
        ll r = n % 26;
        // if (r - 1 >= 0)
        //     result.push_back(alphabets[r - 1]);
        // else
        //     result.push_back('z');
        result.push_back(alphabets[r]);
        if (q == 0)
            break;
        // if (r != 0)
        // {
        //     n = q;
        // }
        // else
        // {
        //     n = q - 1;
        // }
        n = q;
    }
    for (auto itr = result.rbegin(); itr != result.rend(); ++itr)
    {
        cout << *itr;
    }
    cout << endl;
}

Measured memory_bytes: 3100
import sys
from math import atan,pi
def main():
    input = sys.stdin.readline
    a,b,x =map(int, input().split())
    x /= a
    t = 0
    if 2*x < a * b:
        t = atan(b*b/2/x)
    elif 2*x > a * b:
        t = atan((2*a*b-2*x)/a/a)
    else:
        t = pi/4
    ans = t * 180 / pi
    print(ans)


if __name__ == '__main__':
    main()

Measured memory_bytes: 38384
#include <stdio.h>
#include <algorithm>
 
using namespace std;
 
int main(){
    int H,W;
    while(true){
        scanf("%d %d",&H,&W);
        if(H == 0 && W == 0) break;
        for(int i = 0; i < H; i++){
            for(int j = 0; j < W; j++){
                if((i+j)%2 == 0) printf("#");
                else{
                    printf(".");
                }
            }
            printf("\n");
        }
        printf("\n");
    }
}



Measured memory_bytes: 2628
#include <iostream>
#include <vector>
#include <string>

using namespace std;
using ll = long long;

int main() {
	string S;
	cin >> S;
	if (S[S.size() - 1] == 's') cout << S + "es" << endl;
	else cout << S + "s" << endl;
	return 0;
}

Measured memory_bytes: 3604
#include<bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
#define REP2(i,a,b) for(int i=(a);i<(b);i++)
#define ALL(v) (v).begin(),(v).end()
#define INF 2e9
typedef long long ll;

int main()
{
  string s;
  cin>>s;

  int b=0;
  ll ans=0;
  REP(i,s.size()){
    if(s[i]=='B'){
      b++;
    }
    if(s[i]=='W') ans+=b;
  }
  cout<<ans<<endl;

  return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <set>
#include <string>
#include <bitset>
#include <tuple>
#include <queue>
#include <stack>
using namespace std;
#define ll long long
#define fi first
#define se second
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, k, n) for (int i = (int)(k); i <(int)(n); i++)
#define rrep(i, n) for (int i = (int)(n)-1; i >= 0; i--)
#define rREP(i,k,n) for (int i = (int)(n)-1; i >= k; i--)
#define INF 1LL<<32
int main(){
    int n,k;
    string s;
    cin >> n >> k;
    cin >> s;
    int v = 1;
    int ii = 0;
    int ans = 0;
    queue<int> que;
    bool flag = true;
    int j = k+1;
    rep(i,n){
        if(s[i]=='0' && v == 1){
            v *= -1;
            j-=1;
        }
        if(s[i]=='1' && v == -1){
            v *= -1;
            que.push(i);
        }
        if(j<=0) {
            ii = i;
            flag = false;
            ans = ii;
            break;
        }
    }
    if(flag){
        cout << n << endl;
        return 0;
    }
    j = 1;
    REP(i,ii,n){
        if((s[i]=='0' && v == 1) || i==n-1 ){
            if(i==n-1) i+=1;
            v *= -1;
            j-=1;
            if(j<=0){
                // cout << que.front() << ":" << i<< endl;
                ans = max(ans,i-que.front());
                que.pop();
            }
        }
        if(s[i]=='1' && v == -1){
            v *= -1;
            que.push(i);
        }
    }
    cout << ans << endl;
    return 0;
}


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

int main() {
  int n, m;
  cin >> n >> m;
  vector<ll> x(n), y(n), z(n);
  for (int i = 0; i < n; i++) {
    cin >> x[i] >> y[i] >> z[i];
  }
  ll r = 0;
  for (auto sx : {-1, 1}) {
    for (auto sy : {-1, 1}) {
      for (auto sz : {-1, 1}) {
        vector<ll> v(n);
        for (int i = 0; i < n; i++) {
          v[i] = sx * x[i] + sy * y[i] + sz * z[i];
        }
        sort(rbegin(v), rend(v));
        ll s = 0;
        for (int i = 0; i < m; i++) {
          s += v[i];
        }
        r = max(r, s);
      }
    }
  }
  cout << r << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <string>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<ll,ll>PP;
const ll MOD = 1000000007;
int main(){
  ll n,m;cin>>n>>m;
  int ans=n;
  for(int i=1;i<=m;i++){
    ll a;cin>>a;
    ans-=a;
  }
  cout<<max(-1,ans)<<endl;

}


Measured memory_bytes: 3632
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>


using namespace std;
using ll = long long int;

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

#define INF 1000000000

struct entry {
  ll cost;
  ll x;
  ll y;
  ll dir;
  
  bool operator<(const entry & a) const {
    return this->cost < a.cost;
  }

  bool operator>(const entry & a) const {
    return this->cost > a.cost;
  }
};

ll H, W, K;
vector<string> C;
vector<vector<ll>> d[4];


void search(ll x0, ll y0) {
  ll dirs[4][2] = { { 0, 1}, { 0, -1}, { 1, 0}, {-1, 0}};
  priority_queue<entry, std::vector<entry>, greater<entry>> queue;
  queue.push({ 0, x0, y0, 0 });

  while (!queue.empty()) {
    entry e = queue.top();
    queue.pop();

    if (e.cost >= d[e.dir][e.x][e.y]) { continue; }
    d[e.dir][e.x][e.y] = e.cost;


    // go straight
    ll x = e.x + dirs[e.dir][0];
    ll y = e.y + dirs[e.dir][1];

    if (0 <= x && x < H && 0 <= y && y < W && C[x][y] != '@') {
//      cout << e.x << "," << e.y << "," << e.dir << endl;
      queue.push({ e.cost + 1, x, y, e.dir });
    }

    // rotate
    queue.push({  ((e.cost + K - 1) / K) * K, e.x, e.y, (e.dir + 1) % 4 });
  }
}

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  
  cin >> H >> W >> K;

  ll x1, y1, x2, y2;
  cin >> x1 >> y1 >> x2 >> y2;
  x1--; y1--; x2--; y2--;

  rep(j, H) {
    string s; cin >> s;
    C.emplace_back(s);
  }

  rep(j, H) {
    vector<ll> v(W, INF);
    rep(r, 4) {
      d[r].emplace_back(v);
    }
  }

  search(x1, y1);
//  cout << "search complete " << endl;
//  cout << x2 << "," << y2 << endl;
  if (d[0][x2][y2] == INF) {
    cout << -1 << endl;
  } else {
    cout << (d[0][x2][y2] + K - 1) / K << endl;
  }
  return 0;
}

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

#define ll long long
#define Fi first
#define Se second
#define Pb push_back

const int INF = 1e9;
const int MOD = 1e9+7;

#define all(v) v.begin(),v.end()
#define output_s(a) printf("%s\n",(a).c_str())

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define Rep(i,n,m) for(int i=(int)(n);i<(int)(m);i++)
#define RepS(i,n,m) for(int i=(int)(n);i<=(int)(m);i++)
#define RRepS(i,n,m) for(int i=(int)(n);i>=(int)(m);i++)
#define RepA(x) for(auto item:(x))

void CINT(){}
template <class Head,class... Tail>
void CINT(Head&& head,Tail&&... tail){
    cin>>head;
    CINT(move(tail)...);
}    
#define CIN(...) int __VA_ARGS__;CINT(__VA_ARGS__)
#define LCIN(...) ll __VA_ARGS__;CINT(__VA_ARGS__)
#define SCIN(...) string __VA_ARGS__;CINT(__VA_ARGS__)

//library----------------------------------------------



int main() {
    CIN(N);
    int x[N];
    rep(i,N) cin>>x[i];
    int ans=INF;
    RepS(i,1,100){
        int cost=0;
        rep(j,N) cost+=(x[j]-i)*(x[j]-i);
        ans=min(ans,cost);
    }
    printf("%d\n",ans);
    return 0;
}

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

//Math/ModInt
template<long long mod = 1000000007>
struct modint{
	long long a;

	constexpr modint() : a(0){}
	constexpr modint(long long t){
		a = t % mod;
		if(a < 0) a += mod;
	}

	constexpr operator long long() const{ return a; }

	constexpr bool operator==(const modint &x) const{ return a == x.a; }
	constexpr bool operator!=(const modint &x) const{ return a != x.a; }

	constexpr modint operator-() const{ return modint(a ? (mod - a) : 0); }
	constexpr modint operator~() const{ return pow(mod - 2); }

	constexpr modint operator+(const modint &x) const{ return modint(*this) += x; }
	constexpr modint operator-(const modint &x) const{ return modint(*this) -= x; }
	constexpr modint operator*(const modint &x) const{ return modint(*this) *= x; }
	constexpr modint operator/(const modint &x) const{ return modint(*this) /= x; }

	constexpr modint &operator+=(const modint &x){
		a += x.a;
		if(a >= mod) a -= mod;
		return *this;
	}
	constexpr modint &operator-=(const modint &x){
		a -= x.a;
		if(a < 0) a += mod;
		return *this;
	}
	constexpr modint &operator*=(const modint &x){
		a = a * x.a % mod;
		return *this;
	}
	constexpr modint &operator/=(const modint &x){
		a = a * (~x).a % mod; 
		return *this;
	}

	constexpr modint &operator++(){ return (*this) += 1; }
	constexpr modint &operator--(){ return (*this) -= 1; }
	constexpr modint &operator++(int){
		modint tmp = *this;
		(*this) += 1;
		return tmp;
	}
	constexpr modint &operator--(int){
		modint tmp = *this;
		(*this) -= 1;
		return tmp;
	}

	friend ostream &operator<<(ostream &os,const modint &x){
		return os << x.a;
	}
	friend istream &operator>>(istream &is,modint &x){
		long long t;
		is >> t;
		x = modint(t);
		return is;
	}

	constexpr modint pow(long long x) const{
		modint ret = 1,tmp = a;
		for(;x;tmp *= tmp,x >>= 1){
			if(x & 1) ret *= tmp;
		}
		return ret;
	}
};

//Math/Combination
template<class T>
struct Combination{
	vector<T> fact,factinv;
	Combination(int n) : fact(n + 1),factinv(n + 1){
		fact[0] = 1;
		for(int i = 1;i <= n;i++) fact[i] = fact[i - 1] * T(i);
		factinv[n] = ~fact[n];
		for(int i = n;i >= 1;i--) factinv[i - 1] = factinv[i] * T(i);
	}
	T nCr(int n,int r){
		if(r < 0 || n < r) return 0;
		return fact[n] * factinv[r] * factinv[n - r];
	}
};

const int MOD = 1000003;

signed main(){
	int q;
	scanf("%d",&q);
	Combination<modint<MOD>> comb(MOD - 1);
	for(int i = 0;i < q;i++){
		int x,d,n,a;
		scanf("%d %d %d",&x,&d,&n);
		modint<MOD> mx = x,md = d;
		a = mx / md;
		if(!d) printf("%d\n",mx.pow(n));
		else if(n >= MOD || a > (a + n - 1) % MOD) puts("0");
		else printf("%d\n",comb.fact[a + n - 1] * comb.factinv[a - 1] * md.pow(n));
	}
}


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

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {

            string[] あ = Console.ReadLine().Split(' ');
            int numlist = int.Parse(あ[0]);
            int min = int.Parse(あ[1]);
            int max = int.Parse(あ[2]);

            int i;
            int temp;
            int sum = 0;

            for (i = 0; i <= numlist; i++)
            {
                temp = getSomeSum(i);
                if (temp <= max && temp >= min) { sum += i; }
            }

            Console.WriteLine(sum);

        }


        static int getSomeSum(int number)
        {
            int sum=0;

            while (number != 0)
            {
                sum += number % 10;
                number /= 10;
            }


            return sum;
        }


    }
}


Measured memory_bytes: 11092