akhauriyash/Code-Regression huggingface dataset:
N = int(input())
K = int(input())
from functools import lru_cache

@lru_cache(maxsize=1000)
def dp(n, k): #0以上n以下の数で０でない数字がちょうどk個あるもの。
  if k == 0:
    return 1
  elif n == 0:
    return 0
  else:
    n = int(n)
    s = str(n)
    digit = len(s)
    m, fdigit = divmod(n,10)
    if m >= 1:
        return int(dp(m, k-1) * fdigit + dp(m-1, k-1)* (9-fdigit) + dp(m, k))
    elif k == 1:
        return n
    elif k == 2 or k == 3:
        return 0
    else:
        return 1
if K == 0:
    answer = dp(N, K)-1
else:
    answer = dp(N, K)
print(int(answer))

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

#define int long long int
#define rep(a,b,c) for(int a=b;a<c;a++)
#define repm(a,b,c) for(int a=(b-1);a>=c;a--)
#define pb push_back
#define str string
#define sf(a) scanfs("%d",&a)
#define pb push_back
#define mp make_pair
#define Fi first
#define Se second
#define ALL(v) (v).begin(), (v).end()

using namespace std;

const int INF = 1e18 + 9;
const int Mod = 1e9 + 7;
inline int replac(str s){double ans=0;rep(i,0,s.length()){ans+=(s[i]-'0')*pow(10,s.length()-i-1);}return (int)ans;}
inline string numstr(int m){str s="";while(m>0){char c;int a=m/10;if(a>0)a=m%(a*10);else a=m;c=(char)('0'+a);s+=c;m/=10;}str st="";for(int i=s.size()-1;i>=0;i--){st+=s[i];}return st;}
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vii;
int n,m;
vi man;
vii hako;
int memo[10005][505];
int f(int mj=0,int ha=0){
    if(memo[mj][ha]>-1)return memo[mj][ha];
    if(mj>=m||ha>=n){
        if(mj!=0)return memo[mj][ha]=man[mj-1];
        return memo[mj][ha]=0;
    }else{
        int ans=0;
        int you=hako[ha].second;
        int cost=hako[ha].first;
        int mcos=0;
        you=min(m-mj,you);
        ans=f(mj+you,ha+1)-cost;
        return memo[mj][ha]=ans=max(f(mj,ha+1),ans);
    }
}
signed main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> m >> n;
    rep(i,0,10005){
        rep(j,0,505){
            memo[i][j]=-1;
        }
    }
    rep(i,0,m){
        int x;cin >> x;
        man.pb(x);
    }
    rep(i,0,n){
        int x,y;cin >> x >> y;
        hako.pb(mp(y,x));
    }
    sort(ALL(man),greater<int>());
    //sort(ALL(hako));
    rep(i,0,m-1){
        man[i+1]+=man[i];
    }
    cout << f() << endl;
    return 0;
}

Measured memory_bytes: 42828
#include <bits/stdc++.h>
using namespace std;
int N;
int c[505], s[505], f[505];

int main(void){
    cin >> N;
    for (int i=0; i<N-1; i++){
        cin >> c[i] >> s[i] >> f[i];
    }
    
    for (int i=0; i<N; i++){
        int curr_time = s[i];
        curr_time += c[i];
        // cout << curr_time << endl;
        for (int j=i+1; j<N-1; j++){
            // cout << curr_time  % s[j] << endl;
            if (curr_time >= s[j]){
                if(curr_time % f[j] != 0) curr_time += f[j] - (curr_time % f[j]);
            }else{
                curr_time = s[j];
            }
            // cout << curr_time << endl;
            curr_time += c[j];
            
        }
        cout << curr_time << endl;
    }
    
}


Measured memory_bytes: 3576
#include <iostream>
using namespace std;
int main(int argc, char** argv) {
    long long a, b, c; cin >> a >> b >> c;
    if (a%2 && b%2 && c%2) cout << min(min(a*b, b*c), c*a) << endl;
    else cout << 0 << endl;
}


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

using namespace std;
typedef pair<int,int> pii;
typedef long long int ll;

#define INF 1 << 29
#define REP(i,n) for(ll i=0; i<(int)(n); i++)
#define FOR(i,k,n) for(ll i=(k);i<(int)(n);i++)



vector<bool> gen_sosuu(vector<bool> sosuu){
  int size = sosuu.size();
  REP(i,size){
    sosuu[i] = true;
  }
  sosuu[0] = false;
  sosuu[1] = false;
  sosuu[2] = true;
  FOR(i,2,sqrt(size)+1){
    if(sosuu[i] == false) continue;
    for(int j = 2; i*j<size;j++){
      sosuu[i*j] =false;
    }
  }
  return sosuu;
}

int n;
int a[100000];
int sum = 0;

int main(){
  cin >> n;
  REP(i,n){
    cin >> a[i];
  }
  sum += abs(a[0]);
  FOR(i,1,n){
    sum += abs(a[i]-a[i-1]);
  }
  int now = 0;
  REP(i,n-1){
    cout << sum + abs(a[n-1]) - abs(a[i]-now) - abs(a[i]-a[i+1]) + abs(now-a[i+1]) << endl;
    now = a[i];
  }
  cout << sum + abs(a[n-2]) - abs(a[n-1]-now) << endl;
}


Measured memory_bytes: 1664
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int N = 1e7+5;
vector<int> s(N,0);

void foo()
{
  for(ll i=1;i<N;i++)
  {
      for(ll j=i;j<N;j+=i)
      {
        s[j]++;
      }
  }
}

int main() {
  foo();
  int n;
  cin>>n;
  ll ans = 0;
  for(ll i =1;i<=n;i++)
  {
    ans = ans + (s[i]*i);
  }
  cout<<ans<<endl;
  
  return 0;
}

Measured memory_bytes: 42140
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <tuple>
using namespace std;
const int mod = 1000000007;
int main() {	
	int n;
	cin >> n;
	vector<int> nums(2 * n);
	for (int i = 0; i < 2 * n; ++i) {
		cin >> nums[i];
	}
	sort(nums.begin(), nums.end());
	int result = 0;
	for (int i = 2 * n - 1; i >= 1; i = i - 2) {
		result += min(nums[i], nums[i - 1]);
	}
	cout << result << endl;
		
	

}

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

#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;
const int INF = 1e9;

int main() {
  ll n, q, h, s, d, ans = 0;
  cin >> q >> h >> s >> d >> n;
  ans =
      n / 2 * min({8 * q, 4 * h, 2 * s, d}) + (n % 2) * min({4 * q, 2 * h, s});

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


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
using namespace std;
int main()
{
	int kaidan[40];
	kaidan[1] = 1;
	kaidan[2] = 2;
	kaidan[3] = 4;
	for(int i = 4; i <= 30; i++){
        kaidan[i] = kaidan[i-1] + kaidan[i-2] + kaidan[i-3];
	}
    while(1){
        int n;
        cin >> n;
        if(n == 0) break;
        cout << kaidan[n] / 3650 + 1 << endl;
    }

	return 0;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
#include <atcoder/string>
using namespace std;
using namespace atcoder;
/* typedef */
typedef long long ll;
typedef pair<int, int> pii;
/* constant */
const int mod = 1e+9 + 7;
const int INF = 1 << 30;
/* global variables */
/* funciton */
/* main */
int main() {
    static char buf[500'001];
    scanf("%s", buf);
    string s = buf;
    vector<int> sa = suffix_array(s);
    long long answer = 1LL * s.size() * (s.size() + 1) / 2;
    for (auto x : lcp_array(s, sa)) {
        answer -= x;
    }
    printf("%lld\n", answer);
    return 0;
}

Measured memory_bytes: 16140
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		while(scan.hasNext()){
			String line = scan.next();//nextLine?????¨??????????????????????????§???
			if(line.equals("-")){
				scan.close();
				break;
			}
			int m = scan.nextInt();
			for(int i = 0; i < m; i++){
				int h = scan.nextInt();
				String subline1 = line.substring(0, h);
				String subline2 = line.substring(h);
				line = subline2.concat(subline1);
			}
			System.out.println(line);
		}
	}
}

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

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

    int a, b;
    cin >> a >> b;

    int result = 0;
    if(1<=a && a<=9 && 1<=b && b<=9){
        result = a * b;
    }else{
        result = -1;
    }
    cout << result << endl;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
 
int i;
string text;
 
void forChar(void){
    if(i != text.length()){
        i++;
    }
}
 
void forWord(void){
  int len = text.length();
 
  if(i == text.length()) return;
 
  if(text.at(i) == ' '){
    for(;i<len && text.at(i)==' ';i++);
    if(i == len) return;
  }
  for(;i<len && text.at(i)!=' ';i++);
}
 
void backChar(void){
    if(i != 0){
        i--;
    }
}
 
void backWord(void){
  if(i == 0) return;
 
  if(text.at(i-1) == ' '){
    for(;i>0 && text.at(i-1)==' ';i--);
    if(i == 0) return;
  }
  for(;i>0 && text.at(i-1)!=' ';i--);
}
 
void insert(string s){
    text.insert(i,s);
    i += s.length();
}
 
void delChar(void){
    if(i != text.length()){
        text.erase(text.begin()+i);
    }
}
 
void delWord(void){
    int len = text.length();
    int gi=i;
 
    if(i == len) return;
 
    if(text.at(i) == ' '){
        for(;gi<len && text.at(gi)==' ';gi++);
        if(gi == len) return;
    }
    for(;gi<len && text.at(gi)!=' ';gi++);
 
    text.erase(text.begin()+i, text.begin()+gi);
}
 
int main(void){
    int n,m;
    string s,s2;
    char tmp;
 
    cin>>n;
    cin.get();
 
    while(n--){
        getline(cin,text);
        cin>>m;
 
        i=0;
 
        while(m--){
            cin>>s;
            getline(cin,s2);
            s2.erase(s2.begin(),s2.begin()+1);
 
            if(s == "forward"){
                if(s2 == "char"){
                    forChar();
                }
                else{
                    forWord();
                }
            }
            else if(s == "backward"){
                if(s2 == "char"){
                    backChar();
                }
                else{
                    backWord();
                }
            }
            else if(s == "insert"){
                s2.erase(s2.end()-1,s2.end());
                s2.erase(s2.begin(),s2.begin()+1);
                insert(s2);
            }
            else{
                if(s2 == "char"){
                    delChar();
                }
                else{
                    delWord();
                }
            }
        }
        text.insert(i,"^");
        cout<<text<<endl;
    }
 
  return 0;
}

Measured memory_bytes: 1236
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <utility>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int main(){
	int n,h,w;
	scanf("%d%d%d",&n,&h,&w);
	printf("%d\n",(n - h + 1) * (n - w + 1));
	return 0;
}


Measured memory_bytes: 256
N = int(input())
S = input()
ans = []
for i in range(1, N):
    X = S[: i + 1]
    Y = S[i + 1 :]
    setlist = list(set(X)) + list(set(Y))
    ans.append(len(setlist) - len(set(setlist)))
print(max(ans))

Measured memory_bytes: 3060
function main(arg) {
  const array = arg.trim().split("\n");
  const N = parseInt(array[0], 10);
  let counter = 0;
  var AC = (arg.match(/AC/g) || []).length;
  var WA = (arg.match(/WA/g) || []).length;
  var TLE = (arg.match(/TLE/g) || []).length;
  var RE = (arg.match(/RE/g) || []).length;
  // console.log(AC);
  // console.log(WA);
  // console.log(TLE);
  // console.log(RE);
  console.log(
    "AC x " + AC + "\nWA x " + WA + "\nTLE x " + TLE + "\nRE x " + RE
  );

  // while (true) {
  //   counter++;
  //   console.log(array[counter]);
  //   if (counter == N) {
  //     // console.log(counter);
  //     break;
  //   }
  // }
}
main(require("fs").readFileSync("/dev/stdin", "utf8"));
// main(`10
// AC
// AC
// AC
// AC
// AC
// AC
// AC
// AC
// AC
// AC`);
// https://atcoder.jp/contests/abc173/tasks/abc173_a


Measured memory_bytes: 37916
#include <bits/stdc++.h>
 
#define rep(i,n) for(ll i=0;i<n;++i)
#define all_map(itr,mp) for(auto itr=mp.begin();itr!=mp.end();itr++)
#define ALL(a) (a).begin(),(a).end()

using namespace std;
using ll  = long long;
using pll = pair<ll, ll>;

const ll MOD  = 1e9 + 7;
const ll LINF = 1LL << 62;
const int INF = 1e9 + 7;

map<ll, ll> prime;
void Factor(ll n){
    ll sq = sqrt(n) + 1;

    for(int i = 2; i <= sq; ++i){
        sq = sqrt(n) + 1;
        if(n%i == 0){
            if(prime.count(i) == 0)prime[i] = 0;
            while(n%i == 0){
                n /= i;
                prime[i]++;
            }
        }
    }

    if(n != 1){
        if(prime.count(n) == 0)prime[n] = 1;
        else prime[n]++;
    }
}

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

    rep(i, n)Factor(i+1);

    ll over_3, over_5;
    over_3 = over_5 = 0;
    all_map(itr, prime)if(itr->second >= 2){
        over_3++;
        if(itr->second >= 4)over_5++;
    }

    ll ans = (over_5 * (over_5-1)) / 2 * (over_3-2);
    all_map(itr, prime){
        ll cnt = itr->second;
        if(cnt >= 74)ans++;
        if(cnt >= 24)ans += max((ll)0, over_3-1);
        if(cnt >= 14)ans += max((ll)0, over_5-1);
    }

    cout << ans << endl;
}

Measured memory_bytes: 3644
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define eps 1e-9
#define maxp 99940000
#define mod 1000000007
#define pi 3.141592653589793238
#define sin(s) scanf("%lld",&s);
#define sout(s) printf("%lld\n",s);
#define in(s) cin>>s
#define in2(a,b) cin>>a>>b
#define in3(a,b,c) cin>>a>>b>>c
#define vll vector<ll>
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define endl '\n'
#define sp ' '
#define gear_change ios_base::sync_with_stdio(false),cin.tie(0)
#define nfl(i,n) for(i=0;i<n;i++)
#define sfl(i,s,e) for(i=s;i<e;i++)
#define ufl(i,n) for(i=n-1;i>=0;i--)
ll power(ll x,ll y){
    ll ret=1;
    while(y>0){
        if(y&1)
            ret=(ret*x);
        y/=2;
        x=(x*x);
    }
    return ret;
}
string rot(string s){
	string ret="";
	ll i;
	for(i=1;s[i];i++){
		ret+=s[i];
	}
	ret+=s[0];
	return ret;
}
ll power(ll x,ll y,ll p)
{
	ll ret=1;
	while(y>0)
	{
		if(y&1)
			ret=(ret*x)%p;
		y/=2;
		x=(x*x)%p;
	}
	return ret%p;
}
void solve(){
	ld a,v,b,w,t;
	cin>>a>>v>>b>>w>>t;
	ld dis=abs(a-b);
	ld spe=(v-w);
	if(spe*t>=dis){
		cout<<"YES"<<endl;
	}else{
		cout<<"NO"<<endl;
	}
}	
int main(){
	gear_change;
	ll test=1;
	// in(test);
	while(test--){
		solve();
	}
}	


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

int main(){

	int n;
	cin>>n;

	int a[4][3][10]={};	

	for(int i=0;i<n;i++){
		int b,f,r,v;
		cin>>b>>f>>r>>v;
		a[b-1][f-1][r-1]+=v;
	}
	

	for(int i=0;i<4;i++){
		if(i) cout<<"####################"<<endl;

		for(int j=0;j<3;j++){
			for(int k=0;k<10;k++){
				cout<<" "<<a[i][j][k];
			}
			cout<<endl;
		}
	}

return 0;
}



		


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

#define N_MAX 100002
#define ll long long

using namespace std;

int n;

ll m;

vector <int> edges[N_MAX];

vector <int> sons[N_MAX];

bool visited[N_MAX];

void dfs (int node)
{
    visited[node] = true;
    for(int u : edges[node])
        if(visited[u] == false)
        {
            sons[node].push_back(u);
            dfs(u);
        }
}

ll up[N_MAX], down[N_MAX];

void computeDown (int node)
{
    down[node] = 1;
    for(int u : sons[node])
    {
        computeDown(u);
        down[node] = down[node] * (down[u] + 1) % m;
    }
}

void computeUp (int node)
{
    up[node] = (up[node] + 1) % m;
    ll pre = 1;
    for(auto u : sons[node])
    {
        up[u] = up[u] * pre % m;
        pre = pre * (down[u] + 1) % m;
    }
    reverse(sons[node].begin(), sons[node].end());
    ll suf = 1;
    for(auto u : sons[node])
    {
        up[u] = up[u] * suf % m;
        up[u] = up[u] * up[node] % m;
        suf = suf * (down[u] + 1) % m;
    }
    for(auto u : sons[node])
        computeUp(u);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        edges[u].push_back(v);
        edges[v].push_back(u);
    }
    dfs(1);
    computeDown(1);
    for(int i = 2; i <= n; i++)
        up[i] = 1;
    computeUp(1);
    for(int i = 1; i <= n; i++)
        cout << down[i] * up[i] % m << "\n";
    return 0;
}


Measured memory_bytes: 16768
n = int(input())
s = input()
ret = 0
for d in range(1, n - 1):
    l = 0
    for i in range(n - d):
        if s[i] == s[i + d]:
            l += 1
        else:
            l = 0
        ret = max(ret, min(l, d))
print(ret)


Measured memory_bytes: 42220
#include <iostream>
#include <vector>
#include <boost/multiprecision/cpp_int.hpp>
#define rep0(i, n) for(int i=0; i<(int)(n);i++)
typedef int64_t lint;
using namespace std;

int main(){
    lint n, k;
    cin >> n >> k;
    vector<lint> a(n);
    rep0(i, n){
        cin >> a[i];
    }
    lint kk = k * (k - 1) / 2;
    boost::multiprecision::cpp_int ans = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            lint left = 0; //中に
            lint right = 0; //中に
            if(a[i] > a[j]){
                if(i > j)left ++ ;
                if(i < j)right ++ ;
            }
            ans += (right + left) * kk + right * k; //中に
        }
        ans %= 1000000007; //中に
    }
    cout << ans << endl;
}




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

int main()
{
    long long int h,n,a,s=0;
    cin>>h>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a;
        s+=a;
    }
    (s>=h)?cout<<"Yes":cout<<"No";
    return 0;
    
}


Measured memory_bytes: 256
#include <cstdio>

int N, A, B;
int h[100010];

int calc(int x)
{
	//int xx = x;
	long long xx = x;
	int i;
	for(i=0; i<N; i++){
		if(h[i] - B*xx > 0){
			//int y = (h[i] - B*x -1) / (A-B) + 1;
			int y = (h[i] - B*xx -1) / (A-B) + 1;
			x -= y;
			if(x < 0)
				return 0;
		}
	}
	return 1;
}

void solve()
{
	int l=1, r=1000000000;
	int m;
	while(l<=r){
		m = (l+r)/2;
		if(calc(m)==1 && calc(m-1)==0)
			break;
		else if(calc(m)==0)
			l = m+1;
		else
			r = m-1;
	}
	printf("%d\n", m);
}

int main()
{
	int i;
	scanf("%d%d%d", &N, &A, &B);
	for(i=0; i<N; i++)
		scanf("%d", &h[i]);
	solve();
	return 0;
}

Measured memory_bytes: 512
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;

const int maxn=1e5+5;

int n,rt,tot,deg[maxn];
int A[maxn],now[maxn],pre[maxn*2],son[maxn*2];

int read() {
    int x=0,f=1;char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
    for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
    return x*f;
}

void add(int a,int b) {
    pre[++tot]=now[a];
    now[a]=tot,son[tot]=b;
}

ll dfs(int fa,int u) {
    if(deg[u]==1)return A[u];
    ll remain=A[u]<<1;
    for(int p=now[u],v=son[p];p;p=pre[p],v=son[p])
        if(v!=fa) {
            ll tmp=dfs(u,v);
            if(tmp>A[u]) {puts("NO");exit(0);}
            remain-=tmp;
        }
    if(remain<0||remain>A[u]) {puts("NO");exit(0);}
    return remain;
}

int main() {
    n=read();
    for(int i=1;i<=n;i++)
        A[i]=read();
    if(n==2) {
        if(A[1]==A[2])puts("YES");
        else puts("NO");return 0;
    }
    for(int i=1;i<n;i++) {
        int x=read(),y=read();
        add(x,y),add(y,x);deg[x]++,deg[y]++;
        if(deg[x]>1)rt=x;if(deg[y]>1)rt=y;
    }
    if(dfs(0,rt))puts("NO");
    else puts("YES");
    return 0;
}

Measured memory_bytes: 7680
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <cstdio>
#include <ctime>
#include <assert.h>
#include <chrono>
#include <random>
#include <numeric>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
using namespace std;
typedef long long int ll;
typedef unsigned long long ull;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
    return (ull)rng() % B;
}

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

int h=19,w=15;
int n;

char fi[19][15];
vector<pair<int,int>> v;
map<pair<int,int>,int> mp;

bool is_in(int x,int y){
	return 0<=x&&x<h&&0<=y&&y<w;
}

int solve(){
	queue<pair<pair<int,int>,pair<int,int>>> q;
	vector<bool> used(1<<n,false);
	for(int i=0;i<n;i++){
		for(int j=0;j<8;j++){
			auto now=v[i];
			now.first+=dx[j];
			now.second+=dy[j];
			int nx=now.first,ny=now.second;
			if(is_in(nx,ny)&&fi[nx][ny]=='O'&&!used[(1<<n)-1]){
				q.push(make_pair(make_pair((1<<n)-1,0),make_pair(i,j)));
				used[(1<<n)-1]=1;
			}
		}
	}
	while(q.size()){
		auto p=q.front(); q.pop();
		for(int i=0;i<8;i++){
			bool jump=0;
			auto now=p;
			now.first.second++;
			int nx=v[now.second.first].first+dx[now.second.second];
			int ny=v[now.second.first].second+dy[now.second.second];
			now.second.second=i;
			while(is_in(nx,ny)){
				nx+=dx[i],ny+=dy[i];
				if(!is_in(nx,ny)||mp.find(make_pair(nx,ny))==mp.end()||!(now.first.first>>mp[make_pair(nx,ny)]&1)){
					break;
				}
				jump=true;
				now.second.first=mp[make_pair(nx,ny)];
				now.first.first-=(1<<now.second.first);
			}
			if(!jump)continue;
			if(nx==19||(nx==18&&is_in(nx,ny))){
				return now.first.second;
			}
			if(!is_in(nx,ny))continue;
			if(!used[now.first.first]){
				q.push(now);
				used[now.first.first]=1;
			}
		}
	}
	return -1;
}

int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			cin >> fi[i][j];
			if(fi[i][j]=='X'){
				mp[make_pair(i,j)]=v.size();
				v.push_back(make_pair(i,j));
			}
		}
	}
	n=v.size();
	cout << solve() << endl;
}


Measured memory_bytes: 3320
'use strict'

const main = input => {
	const args = input.trim().split(' ').map(Number)
	const t1 = args[0] * args[1]
	const t2 = args[2] * args[3]
	if (t1 >= t2) console.log(t1)
	else console.log(t2)
}

main(require('fs').readFileSync('/dev/stdin', 'utf8'))


Measured memory_bytes: 7372
q = int(input())
l = list(range(2, 10**5+1))
prime = [1]*(10**5+1)
prime[0], prime[1] = 0, 0
temp = [0]*(10**5+1)
counts = [0]*(10**5+1)
ans = 0
for i in range(2, int((10**5)**0.5) + 1):
  if not prime[i]:
    continue

  for j in range(i*2, int(10**5) + 1, i):
    prime[j] = 0

for i in range(2, 10**5):
  if prime[i] == 1 and prime[(i+1)//2] == 1:
    temp[i] = 1

for i in range(1, 10**5+1):
  temp[i] += temp[i-1]

for i in range(q):
  l, r = map(int, input().split())
  print(temp[r]-temp[l-1])

Measured memory_bytes: 11636
#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
struct Node{
	int key;
	Node *parent, *left, *right;
	Node():parent(NULL),left(NULL),right(NULL),key(0){ }
};
Node *root=NULL;int m,cnt=0;
Node * insert(int k,Node *r){
	if(!r){
		r=new Node;
		r->key=k;
	}else if(k>r->key) {
		r->right=insert(k,r->right);
	}else {
		r->left=insert(k,r->left);
	}
	return r;
}
void inorder(Node * r){
	if(!r)return;
	inorder(r->left);
	cout<<" "<<r->key;
	inorder(r->right);
}
void preorder(Node *r){
	if(!r)return ;
	cout<<" "<<r->key;
	preorder(r->left);
	preorder(r->right);
}
void print(){
	cnt=0;
	inorder(root);
	putchar('\n');
	cnt=0;
	preorder(root);
	putchar('\n');
}
bool find(int k,Node * r){
	if(!r) return false;
	if(k==r->key)return true;
	bool flag=false;
	if(k>r->key) flag|=find(k,r->right);
	else flag|=find(k,r->left);
	return flag;
}
Node * find_min(Node * r){
	if(!r) return NULL;
	if(!r->left) return r;
	return find_min(r->left);
}
Node * find_max(Node * r){
	if(!r) return NULL;
	if(!r->right) return r;
	return find_max(r->right);
}
Node * dlt(int k,Node * r){
	if(!r) return NULL;
	if(k>r->key) r->right=dlt(k,r->right);
	else if(k<r->key) r->left=dlt(k,r->left);
	else {
		if(r->left && r->right){
			Node * temp=find_min(r->right);
			r->key=temp->key;
			r->right=dlt(r->key,r->right);
		}else {
			Node * temp=r;
			if(! r->left) r=r->right;
			else if( ! r->right) r=r->left;
			delete temp;
		}
	}
	return r;
}
int main(){
	int key;
	string s;
	cin>>m;
	for(int i=0;i<m;i++){
		cin>>s;
		if(s=="insert"){
			cin>>key;
			root=insert(key,root);
		}else if(s=="print"){
			print();
		}else if(s=="find"){
			cin>>key;
			cout<< (find(key,root)?"yes":"no") <<endl; 
		}else if(s=="delete"){
			cin>>key;
			root=dlt(key,root);
		}
	}
	return 0;
}


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

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

    int N, K;
    cin >> N >> K;
    vector<int> l(N);

    rep(i, N) cin >> l[i];

    sort(l.begin(), l.end(), greater<int>());

    int res = 0;
    rep(i, K) res += l[i];

    cout << res << "\n";
}

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

const int MAXN = 64;
int mem[MAXN];

vector<int> split(int y) {
  vector<int> res;
  for(int k = 0; (k|y); y >>= 1) {
    if(y & 1) {
      ++k;
    } else {
      if(k) {
        res.push_back(k);
        k = 0;
      }
    }
  }
  return res;
}

int grundy(int n) {
  int &res = mem[n];
  if(res != -1) return res;
  set<int> s;
  int a = (1<<n)-1;
  for(int x = 1; x <= a; ++x) {
    vector<int> v = split(a - x);
    int ni = 0;
    for(int j = 0; j < v.size(); ++j) {
      ni ^= grundy(v[j]);
    }
    s.insert(ni);
  }
  res = 0;
  while(s.count(res)) ++res;
  return res;
}

int toDec(int p, string s) {
  reverse(s.begin(), s.end());
  int res = 0;
  for(int i = 0, b = 1; i < s.size(); ++i, b *= p) {
    int a = 
      isdigit(s[i]) ? s[i]-'0' : isupper(s[i]) ? s[i]-'A'+10 : s[i]-'a'+36;
    res += a * b;
  }
  return res;
}

int main() {
  fill(mem, mem+MAXN, -1);
  for(int n; cin >> n;) {
    int x = 0;
    for(int i = 0; i < n; ++i) {
      int p;
      string s;
      cin >> p >> s;
      vector<int> v = split(toDec(p, s));
      for(int j = 0; j < v.size(); ++j) {
        //x ^= v[j];
        x ^= grundy(v[j]);
      }
    }
    if(x) cout << "win" << endl;
    else cout << "lose" << endl;
  }
  return 0;
}

Measured memory_bytes: 1224
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
const int INF = 1e9;
const int MAX_V = 300000;

int m, n;
struct Flow{
    struct edge{
        int to, cap, rev;
    };
    vector<edge> G[MAX_V];//隣接リスト
    bool used[MAX_V];

    void add_edge(int from, int to, int cap){
        G[from].push_back((edge){to, cap, (int)G[to].size()});//from -> to
        G[to].push_back((edge){from, 0, (int)G[from].size() - 1});//to -> from
    }

    //増加パスを探す
    int dfs(int v, int t, int f){
        if(v == t) return f;
        used[v] = true;
        for (int i = 0; i < G[v].size(); ++i){
            edge &e = G[v][i];
            if(!used[e.to] && e.cap > 0){
                int d = dfs(e.to, t, min(f, e.cap));
                if(d > 0){
                    e.cap -= d;
                    G[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }
    //sからtへの最大流
    int max_flow(int s, int t){
        int flow = 0;
        while(1){
            memset(used, 0, sizeof(used));
            int f = dfs(s, t, INF);
            if(f == 0) return flow;
            flow += f;
        }
    }
};

int b[510], r[510];
int main(void){
    while(1){
        cin >> m >> n;
        if(m == 0 && n == 0) return 0;
        rep(i, m) cin >> b[i];
        rep(i, n) cin >> r[i];
        int s = m + n, t = m + n + 1;
        Flow mf;
        //s -> b
        rep(i, m){
            mf.add_edge(s, i, 1);
        }
        //r -> t
        rep(i, n){
            mf.add_edge(m + i, t, 1);
        }
        //b -> r
        rep(i, m)rep(j, n){
            if(__gcd(b[i], r[j]) > 1){//1以上の約数を持つ
                mf.add_edge(i, m + j, 1);
            }
        }
        printf("%d\n", mf.max_flow(s, t));
    }
}


Measured memory_bytes: 14696
#include <iostream>
#include <vector>

using namespace std;

int main(){
    vector<int> n(5);
    for(int i = 0; i < 5; i++){
        cin >> n[i];
    }
    int total = 0;
    for(int i = 0; i < 5; i++){
        if(n[i] < 40){
            total += 40; //40点以下は一律40点としてカウント
        }
        else{
            total += n[i];
        }
    }
    cout << total / 5 << endl;
}


Measured memory_bytes: 3116
#include <iostream>

int main()
{
    int case_cnt = 1;
    int in;
    while (1) {
        std::cin >> in;
        if (in == 0) {
            break;
        }

        std::cout << "Case " << case_cnt++ << ": " << in << std::endl;
    }

    return 0;
}

Measured memory_bytes: 1160
#python3 

def main():
    n, m = map(int, input().split())
    data = []
    for _ in range(m):
        x, y = map(int, input().split())
        data.append((x-1, y))
    #矛盾した条件が存在するときは-1を返して終了する
    for i in range(m):
        for j in range(i+1, m):
            i1, v1 = data[i] 
            i2, v2 = data[j]
            if (i1 == i2) and (v1 != v2):
                print(-1)
                return 

    candidates = []
    for candidate in range(1000):
        #cnadidateが条件を満たすかをもつflag
        #条件を満たす値をcandidatesにappendする
        flag = True
        cand = list(str(candidate))
        k = len(cand)
        #n桁でないなら候補ではない
        if (k != n):
            continue
        for i in range(m):
            keta_i = data[i][0]
            keta_v = data[i][1]
            if int(cand[keta_i]) != int(keta_v):
                flag = False
        if flag:
            candidates.append(cand)

    if candidates:
        ans = ''.join(candidates[0])
        print(ans)
    else:
        print(-1)
main()

Measured memory_bytes: 3064
import java.util.Scanner

import scala.io.StdIn._

object Main extends App {

  val Array(h,w,k) = readLine().split(" ").map(_.toInt)
  val C = Array.fill(h)(readLine().split(""))

  def solve() = {
    var ans = 0L
    for(is <- 0 until 1 << h; js <- 0 until 1 << w) {
      var cnt = 0
      for(i <- 0 until h; j <- 0 until w) {
        if(!isBitOn(is,i) && !isBitOn(js,j) && C(i)(j) == "#") cnt += 1
      }
      if(cnt == k) ans += 1
    }
    ans
  }

  def isBitOn(num: Int, digit: Int): Boolean =
    (num & (1 << digit)) != 0


  println(solve())

}



Measured memory_bytes: 54944
#include<stdio.h>

int main(){
	int H, W;
	int i = 0, j = 0;
	char c;
	int count = 0;
	scanf("%d %d\n", &H, &W);
	for( i = 0; i < H; i++ ){
		do{
			scanf("%c", &c);
			if( c == '#' ){ count++; }
		}while( c != '\n' );
	}
	if( count == H + W - 1 ){
		printf("Possible\n");
	}else{
		printf("Impossible\n");
	}
	return 0;
}

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

int dp[100001];
vector<int> num = {6, 9, 36, 81, 216, 729, 1296, 6561, 7776, 46656, 59049};

int loc(int i) {
	if (dp[i] != -1) return dp[i];
	int ret = 987654321;
	int j = 0;
	while (j < num.size() && num[j] <= i) {
		ret = min(ret, loc(i - num[j]) + 1);
		j++;
	}
	return dp[i] = ret;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	memset(dp, -1, sizeof(dp));
	dp[0] = 0;
	for (int i = 1; i <= 5; ++i) dp[i] = i;
	
	int n;
	cin >> n;
	
	cout << loc(n);
}

Measured memory_bytes: 1152
import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;

void main() {
    auto N = readln.chomp.to!int;
    auto A = readln.split.map!(to!long).array;

    if (N == 2) {
        A.reduce!max.writeln;
        return;
    }

    auto L = new long[](N);
    auto R = new long[](N);

    L[0] = A.front;
    R[N-1] = A.back;

    foreach (i; 1..N) L[i] = gcd(L[i-1], A[i]);
    foreach_reverse (i; 0..N-1) R[i] = gcd(R[i+1], A[i]);

    long ans = 1;

    foreach (i; 0..N) {
        long l = i == 0 ? 0 : L[i-1];
        long r = i == N - 1 ? 0 : R[i+1];
        ans = max(ans, gcd(l, r));
    }

    ans.writeln;
}


Measured memory_bytes: 7044
using System;
using System.Linq;
using System.Collections.Generic;

namespace Algorithm
{
    class Program
    {
        static void Main(string[] args)
        {
            var l = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int A = l[0], B = l[1], C = l[2];

            if (C >= A && C <= B) Console.WriteLine("Yes");
            else Console.WriteLine("No");
        }
    }
}


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

int main(){

    int n;
    cin >> n;

    vector<int> dp(n + 1);

    // 順列で初期化
    iota(dp.begin(),dp.end(), 0);

    // dp[i]: i円引き出すためにかかる最小のコスト
    // 貰うDPをする

    dp[0] = 0;

    for(int i = 1; i < n + 1; ++i){
        
        int six_pow = 6;

        while(i - six_pow >= 0){

            dp[i] = min(dp[i], dp[i - six_pow] + 1);
            six_pow *= 6;
        }

        int nine_pow = 9;

        while(i - nine_pow >= 0){

            dp[i] = min(dp[i], dp[i - nine_pow] + 1);
            nine_pow *= 9;
        }
    }

    cout << dp[n] << endl;


    return 0;
}

Measured memory_bytes: 640
n,m = map(int,input().split())
h = list(map(int,input().split()))
x = [list(map(int,input().split())) for nesya in range(m)]
k = [1]*n
for route in x:
  h1 = route[0]-1
  h2 = route[1]-1
  if h[h1] < h[h2]:
    k[h1] = 0
  elif h[h1] > h[h2]:
    k[h2] = 0
  else:
    k[h1] = 0
    k[h2] = 0
print(sum(k))

Measured memory_bytes: 32004
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int main(void){
    int n,l; cin>>n>>l;
    vector<string> s(n);
    for(int i=0;i<n;i++) cin>>s[i];
    sort(s.begin(),s.end());
    for(int i=0;i<n;i++) cout<<s[i];
    cout<<endl;
}


Measured memory_bytes: 256
cx1, cy1, r1 = gets.split.map(&:to_i)
cx2, cy2, r2 = gets.split.map(&:to_i)
d = (((cx1-cx2).abs)**2 + ((cy1-cy2).abs)**2)**(1/2.0)

if d > r1 + r2
  puts "4"
elsif d == r1+ r2
  puts "3"
elsif (r1-r2).abs < d && r1+r2
  puts "2"
elsif (r1-r2).abs == d
  puts "1"
elsif d < (r1 - r2).abs
  puts "0"
end


Measured memory_bytes: 6928
#include <bits/stdc++.h>
 
#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)
 
#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=(int)(a)-1;i>=(int)(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)
 
#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define bit(n) (1LL<<(n))
 
// #define DEBUG
 
#ifdef DEBUG
    #define dump(...) fprintf(stderr, __VA_ARGS__)
#else
    #define dump(...)
#endif
 
template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}
 
using namespace std;
using ll=long long;
using vi=vector<int>;
using vll=vector<ll>;
 
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int inf = INT_MAX;
const ll INF = LLONG_MAX;
const ll MOD = 1000000007LL;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
 
ll extgcd(ll a,ll b,ll& x,ll& y){x=1,y=0;ll g=a;if(b!=0) g=extgcd(b,a%b,y,x),y-=a/b*x;return g;}
ll ADD(const ll &a, const ll &b, const ll mod=MOD) { return (a+b)%mod;}
ll SUB(const ll &a, const ll &b, const ll mod=MOD) { return (a-b+mod)%mod;}
ll MUL(const ll &a, const ll &b, const ll mod=MOD) { return (1LL*a*b)%mod;}
ll DIV(const ll &a, const ll &b, const ll mod=MOD) {ll x,y; extgcd(b,mod,x,y);return MUL(a,(x+mod)%mod,mod);}
 
int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n, m, L; cin >> n >> m >> L;
    using Edge = tuple<int, int>;
    vector<vector<Edge>> G(n);
    rep(_, m){
        int a, b, c; cin >> a >> b >> c;
        a--, b--;
        if(c > L) continue;
        G[a].emplace_back(Edge(b, c));
        G[b].emplace_back(Edge(a, c));
    }

    using S = tuple<int, int, int>;
    S infS = S(inf, -1, -1);
    vector<vi> res(n, vi(n, inf));

    rep(u, n){
        priority_queue<S, vector<S>, greater<S>> q;
        q.push(S(0, 0, u));
        vector<S> d(2 * n, infS);
        d[u] = S(0, 0, u); d[n+u] = S(1, 0, n+u);

        while(q.size()){
            auto curS = q.top(); q.pop();
            int num, l, v; tie(num, l, v) = curS;

            if(d[v] != curS) continue;

            chmin(res[u][v % n], num);

            for(auto& e : G[v % n]){
                int nv, c; tie(nv, c) = e;
                int nl = l + c;
                int nnum = num;
                if(nl > L) continue;

                // not use
                auto nxtS = S(nnum, nl, nv);
                if(chmin(d[nv], nxtS)){
                    q.push(nxtS);
                }

                // use
                nnum++;
                nl = 0;
                nv += n;
                nxtS = S(nnum, nl, nv);
                if(chmin(d[nv], nxtS)){
                    q.push(nxtS);
                }
            }
        }
    }

    int Q; cin >> Q;
    rep(_, Q){
        int a, b; cin >> a >> b;
        a--, b--;

        int val = res[a][b];
        if(val == inf) val = -1;
        cout << val << endl;
    }

    return 0;
}


Measured memory_bytes: 2640
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep2(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
const ll INF = 1LL<<60;
const ll MOD = 1e9+7;


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll h,w,k;cin>>h>>w>>k;
    vector<string> cake(h);
    rep(i,h){
        string s;cin>>s;
        cake[i]=s;
    }
    vector<bool> incs(h);
    int cnt = 1;
    
    vector<vector<int>> op(h,vector<int>(w,0));
    vector<int> next_inc(h,-1);


    rep(i,h){
        int inc = 0;
        rep(j,w){
            if(cake[i][j]=='#')inc++;
        }
        if(cnt==k+1){op[i]=op[i-1];next_inc[i]=i;continue;}
        if(!inc)continue;
        int inc1 = 0;
        rep(j,w){
            if(cake[i][j]=='#'){inc1++;cnt++;}
            if(inc1==0)op[i][j]=cnt;
            else op[i][j]=cnt-1;
        }
        for(int ii = i; ii>=0&&next_inc[ii]==-1; ii--){
            next_inc[ii] = i;
        }
        
    }
    

    rep(i,h){
        rep(j,w){
            cout<<op[next_inc[i]][j]<<" ";
        }
        cout<<endl;
    }

    
    return 0;
}

Measured memory_bytes: 1280
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
 
/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
    sizeは(int)とキャストしよう
    ごちゃごちゃ場合分けを考える前に全探索は考えましたか？
*/

// const ll mod = 1e9+7;

// void chmod(ll &M){
//     if(M >= mod) M %= mod;
//     else if(M < 0){
//         M += (abs(M)/mod + 1)*mod;
//         M %= mod;
//     }
// }

int main(){
    int N; cin >> N;
    vector<ll> a(N+1), b(N);
    for(int i=0; i<N+1; ++i) cin >> a[i];
    for(int i=0; i<N; ++i) cin >> b[i];

    ll ans = 0;
    for(int i=N-1; i>=0; --i){
        
        if(a[i+1] >= b[i]){
            a[i+1] -= b[i];
            ans += b[i];
            b[i] = 0;
        }
        else{
            ans += a[i+1];
            b[i] -= a[i+1];
            ans += min(a[i], b[i]);
            a[i] -= min(a[i], b[i]);
        }
        
    }

    cout << ans << endl;
}

Measured memory_bytes: 1792
#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(){
  int n;
  cin >> n;
  int d[n];
  rep(i, n) cin >> d[i];
  sort(d, d+n);
  cout << d[n/2] - d[n/2-1] << endl;
  return 0;
}


Measured memory_bytes: 640
def main():
    N = int(input())
    S = input()
    ok, ng = 0, N + 1
    while abs(ok - ng) > 1:
        x = (ok + ng) // 2
        check = set()
        for i in range(N - x + 1):
            check.add(S[i: i + x])
            if S[i + x: i + 2 * x] in check:
                ok = x
                break
        else:
            ng = x

    print(ok)


if __name__ == '__main__':
    main()


Measured memory_bytes: 159752
#include<stdio.h>

int main()
{
	int dset,max,sum = 0;/*データ数,最大値,２乗合計*/
	int tri[3],jdg[1000];/*辺,判定*/
	int i,j,es;

	do
	{
		scanf("%d",&dset);
	}while(dset<1 || dset>1000);

	for(i=0;i<dset;i++)
	{
		do
		{
			scanf("%d %d %d",tri,tri+1,tri+2);
			es = 0;
			max = 0;
			sum = 0;
			
			for(j=0;j<3;j++)/*範囲内にあるか調査*/
			{
				if(tri[j]<1 || tri[j]>1000)
				{
					es = 1;
					break;
				}
				else if(max<tri[j])
				{
					max = tri[j];
				}
				
				sum += tri[j]*tri[j];
			}
		}while(es); 

		if((2*max*max)==sum)
			jdg[i]=1;
		else
			jdg[i]=0;

	}

	for(i=0;i<dset;i++)
	{
		if(jdg[i])
			printf("YES\n");
		else
			printf("NO\n");
	}

	return 0;
}

Measured memory_bytes: 580
import itertools
N, M, Q = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(Q)]
ans = 0
for i in itertools.combinations_with_replacement(range(1,M+1),N):
    tmp = 0
    for item in arr:
        if i[item[1]-1] - i[item[0]-1] == item[2]:
            tmp += item[3]
    ans = max(ans,tmp)
print(ans)

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

int main(){
    int N;
    cin >>N;
    string data[N][3];
    string temp1,temp2;

    for (int i = 0; i < N; i++){
        cin >>data[i][0]>>data[i][1];
        data[i][2]=to_string(i+1);
    }
    
    for (int i = 0; i < N-1; i++){
        for (int j = N-1; j > i; j--){

            if( data[j][0] < data[j-1][0] ){
                
                temp1=data[j][0];
                data[j][0]=data[j-1][0];
                data[j-1][0]=temp1;

                temp1=data[j][1];
                data[j][1]=data[j-1][1];
                data[j-1][1]=temp1;

                temp1=data[j][2];
                data[j][2]=data[j-1][2];
                data[j-1][2]=temp1;

            }else if(data[j][0] == data[j-1][0]){

                if((atoi(data[j][1].c_str())) > (atoi(data[j-1][1].c_str()))){

                    temp1=data[j][0];
                    data[j][0]=data[j-1][0];
                    data[j-1][0]=temp1;

                    temp1=data[j][1];
                    data[j][1]=data[j-1][1];
                    data[j-1][1]=temp1;

                    temp1=data[j][2];
                    data[j][2]=data[j-1][2];
                    data[j-1][2]=temp1;
                }

            }
        
        }
        
    }

    for (int i = 0; i < N; i++){
        cout << data[i][2] <<endl;
    }
    
    
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define all(sdk) sdk.begin(),sdk.end()
#define mll map<int, int>
#define pb push_back
#define rep(i,a,b) for(int i=a;i<b;++i)
#define repd(i,a,b) for(int i=a;i>=b;--i)
#define mp make_pair
#define hell 1000000007
#define endl '\n'
#define vvll vector<vector<int> >
#define vll vector<int>
#define mint map<int,int> 
#define sz(x) (int)x.size()
#define sll set<int>
#define pll pair<int,int>
#define F first
#define S second

int n;
int arr[3005];
int dp[3005][3005];

int find(int l, int r){
	if(l>r)
		return -1;

	if(dp[l][r]!=-1)
		return dp[l][r];

	if(l==r){
		return dp[l][r] = arr[l];
	}

	else
		return dp[l][r] = max(arr[l]-find(l+1,r), arr[r]-find(l,r-1));

}

void solve(){
	
	cin>>n;
	rep(i,0,n)
		cin>>arr[i];

	memset(dp,-1,sizeof dp);
	cout<<find(0,n-1)<<endl;;
}
signed main(){
    //freopen("output.txt","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    srand (static_cast <unsigned> (time(0)));
    int t=1;
    while(t--){
        solve();
    }
    return 0;
}

Measured memory_bytes: 70912
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(ri,n) for(int ri = (int)(n-1); ri >= 0; ri--)
#define rep2(i,x,n) for(int i = (int)(x); i < (int)(n); i++)
#define repit(itr,x) for(auto itr = x.begin(); itr != x.end(); itr++)
#define rrepit(ritr,x) for(auto ritr = x.rbegin(); ritr != x.rend(); ritr++)
#define ALL(n) begin(n), end(n)
using ll = long long;
using namespace std;

int main(){
	int n, z, w;
	cin >> n >> z >> w;
	vector<int> a(n);
	rep(snip_i, n) cin >> a.at(snip_i);
	if(n == 1){
		int ans = fabs(a.at(0) - w);
		cout << ans << endl;
		return 0;
	}
	int ans = fabs(a.back() - w);
	int add = fabs(a.at(n-2) - a.at(n-1));
	ans = max(ans, add);
	cout << ans << endl;
	return 0;
}

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

int mod = 1000000007;
int64_t large = 9223372036854775807;

int main()
{
    int N, X;
    cin >> N >> X;
    vector<int> list(N);
    for (int i = 0; i < N; i++)
        cin >> list[i];

    int count = 1, now = 0;
    for (int i = 0; i < N; i++)
    {
        now = now + list[i];
        if (now <= X)
            count++;
    }
    cout << count;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=3005;
ll dp[N][N][2],a[N],n;
ll solve(ll l,ll r,ll turn){
    if(l>r)return 0;
    if(dp[l][r][turn]!=-1)return dp[l][r][turn];
    ll &ans=dp[l][r][turn];
    ll v1 = solve(l+1,r,1-turn);
    ll v2 = solve(l,r-1,1-turn);
    if(turn==0)ans=max(v1+a[l] , v2+a[r]);
    else ans=min(v1-a[l] , v2-a[r]);
    return ans;
}
int main(){
    ios_base:: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin>>n;
    for(ll i=1;i<=n;i++)cin>>a[i];
    memset(dp,-1,sizeof(dp));
    cout<<solve(1,n,0);
}

Measured memory_bytes: 141568
#include <cstdio>

using namespace std;

int main() {
  int x, y;
  scanf("%d%d", &x, &y);
  int ans = 0;
  if (x <= 3) {
    ans += (4 - x) * 100'000;
  }
  if (y <= 3) {
    ans += (4 - y) * 100'000;
  }
  if (x == 1 && y == 1) {
    ans += 400'000;
  }
  printf("%d\n", ans);
}


Measured memory_bytes: 128
#include<stdio.h>

int main(void)
{
	int i,j,k,n,m,a[5000],b[5000],dp[5000],S=0;
	
	scanf("%d%d",&n,&m);
	for(i=0;i<=n-1;i++)
	{
		scanf("%d",&a[i]);
	}
	for(i=0;i<=m-1;i++)
	{
		scanf("%d",&b[i]);
		dp[i]=0;
	}
	for(i=0;i<=m-1;i++)
	{
		k=i;
		for(j=0;j<=n-1;j++)
		{
			if(b[k]==a[j])
			{
				dp[i]++;
				k++;
			}
		}
		if(S<=dp[i]) S=dp[i];
	}
	printf("%d\n",S);
	return 0;
}

Measured memory_bytes: 656
S = input()
S = [int(i) for i in list(S)]

a = []
c = []
b = True
for i in range(len(S)):
    if b:
        a.append(1)
        c.append(0)
        b=False
    else:
        a.append(0)
        c.append(1)
        b=True

combined1 = [abs(x-y) for (x, y) in zip(S, a)]
combined2 = [abs(x-y) for (x, y) in zip(S, c)]

if len(S)==1:
    print(0)
else:
    print(min(sum(combined1), sum(combined2)))

Measured memory_bytes: 7524
N = int(input())
import math

# 素数判定関数
def isPrime(num):
    # 2未満の数字は素数ではない
    if num < 2: return False
    # 2は素数
    elif num == 2: return True
    # 偶数は素数ではない
    elif num % 2 == 0: return False

    # 3 ~ numまでループし、途中で割り切れる数があるか検索
    # 途中で割り切れる場合は素数ではない
    for i in range(3, math.floor(math.sqrt(num))+1, 2):
        if num % i == 0:
            return False

    # 素数
    return True

# 素数判定
def callIsPrime(input_num=1000):
    numbers = []
    # ループしながら素数を検索する
    for i in range(1, input_num):
        if isPrime(i):
            numbers.append(i)

    # 素数配列を返す
    return numbers

# 関数の呼び出し
#print(callIsPrime(55556))
A = callIsPrime(55556)
B = [0] * 56
j = 0
for i in range(1, len(A)):
  if A[i] % 5 == 1:
    B[j] = A[i]
    j += 1
  if j == 56:
    break
    
#print(B)
for i in range(N):
  print(B[i], end = " ")
print("")

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

using namespace std;


typedef long long int64;
const int mod = 1e9 + 7;

struct BinaryIndexedTree
{
  vector< int > data;

  BinaryIndexedTree(int sz)
  {
    data.assign(++sz, 0);
  }

  int sum(int k)
  {
    int ret = 0;
    for(++k; k > 0; k -= k & -k) (ret += data[k]) %= mod;
    return (ret);
  }

  void add(int k, int x)
  {
    for(++k; k < data.size(); k += k & -k) (data[k] += x) %= mod;
  }

  int get(int k)
  {
    return ((sum(k) - sum(k - 1) + mod) % mod);
  }
};


// i 番目を見ていて A に最後に j を追加した時
int getLastB(int i, int j)
{
  if(i - 1 == j) return (j - 1);
  return (j + 1);
}


int main()
{
  int64 N, A, B, X[100000];

  int64 AA[100000], BB[100000];

  cin >> N >> A >> B;
  for(int i = 0; i < N; i++) {
    cin >> X[i];
    AA[i] = upper_bound(X, X + i + 1, X[i] - A) - X;
    BB[i] = upper_bound(X, X + i + 1, X[i] - B) - X;
  }

  BinaryIndexedTree dp1(N), dp2(N);
  dp1.add(0, 1);
  dp2.add(0, 1);

  int aa = 0, bb = 0;

  for(int i = 1; i < N; i++) {
    // 最初に追加したところ
    int s = dp2.sum(AA[i]), t = dp1.sum(BB[i]);
    dp1.add(i, s); // B -> A
    dp2.add(i, t); // A -> B
    if(X[i] - X[i - 1] < A) {
      for(int j = i - 1; j >= aa; j--) dp1.add(j, mod - dp1.get(j));
      aa = i;
    }
    if(X[i] - X[i - 1] < B) {
      for(int j = i - 1; j >= bb; j--) dp2.add(j, mod - dp2.get(j));
      bb = i;
    }
  }

  cout << (dp1.sum(N - 1) + dp2.sum(N - 1)) % mod << endl;
}


Measured memory_bytes: 3456
#include <iostream>
#include <algorithm>
#include <string>
#include <numeric>
#include <vector>
#include <queue>
#define rep(i,n) for(int i=0;i<n;i++)
#define ll long long int
#define ii pair<int,int>
#define MAX 1000000007

using namespace std;


int main(void){
	int n;
	cin >> n;
	int a[n+2];
	ll cost = 0;
	a[0] = 0;
	a[n+1] = 0;
	rep(i,n){
		cin >> a[i+1];
		cost += abs(a[i+1]-a[i]);
	}
	cost += abs(a[n+1]-a[n]);

	rep(i,n){
		cout << cost-(abs(a[i+1]-a[i])+abs(a[i+2]-a[i+1]))+abs(a[i+2]-a[i]) << endl;
	}
	return 0;

}


Measured memory_bytes: 1664