akhauriyash/Code-Regression huggingface dataset:
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
using namespace std;

int main()
{
    const char *YES = "YES";
    const char *NO = "NO";

    char C1[4];
    char C2[4];

    if (scanf("%s%s", C1, C2) < 2) return 0;

    if (C1[0] == C2[2]
        && C1[1] == C2[1]
        && C1[2] == C2[0]) printf("%s\n", YES);
    else printf("%s\n", NO);

    return 0;
}


Measured memory_bytes: 128
N,W=map(int,input().split())
dp=[0]*(W+1)
L = sorted([list(map(int,input().split())) for i in range(N)])
s=0
 
for w, v in L:
    s+=w
    for j in range(min(W,s),w-1,-1):
        if dp[j-w]+v > dp[j]: dp[j]=dp[j-w]+v
    
print(max(dp))

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

#define full(x,n) x,x+n+1
#define full(x) x.begin(),x.end()
#define finish return 0

#define putb push_back
#define f first
#define s second

#define putf push_front
#define gainb pop_back

#define gainf pop_front
#define len(x) (int)x.size()

// 1/b%mod=b^(m-2)%mod

typedef double db;
typedef long long ll;

const ll ary=1e5+5;
const ll mod=1e9+7;
const ll inf=1e18;

using namespace std;
string s;
map<char,ll> mp;
ll ans;
int main(){
	cin>>s;
	for(int i=len(s)-1;i>=0;i--){
		ans+=mp[s[i]];
		for(char c='a';c<='z';c++){
			if(c!=s[i]){
				mp[c]++;
			}
		}
	}
	cout<<ans+1;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define loop(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  loop(i,0,n)
#define all(c) c.begin(),c.end()
#define vi vector<int>
#define vl vector<ll>
#define pll pair<ll,ll>
#define vpll vector<pll>

void Acout(int A[],int N){
    rep(i,N){
        if(i)cout<<" ";
        cout<<A[i];
    }
    cout<<endl;
}

int main(){
    stack<int> s1;
    stack<pair<int,int> >s2;
    char ch;
    int sum=0;

    for(int i=0;cin>>ch;i++){
        if(ch=='\\')s1.push(i);
        else if(ch=='/' && s1.size()>0){
            int j=s1.top();s1.pop();
            sum += i-j;
            int a = i-j;
            while(s2.size()>0 && s2.top().first>j){
                a += s2.top().second;s2.pop();
            }
            s2.push(make_pair(j,a));
        }
    }

    vi ans;
    int t=0;
    while(s2.size()>0){ans.push_back(s2.top().second);s2.pop();}
    reverse(all(ans));
    cout<<sum<<endl;
    cout<<ans.size();
    for(int i=0;i<ans.size();i++){
        cout<<" ";
        t +=ans[i];
        cout<<ans[i];
    }
    cout<<endl;
}


Measured memory_bytes: 3176
// ITP1_9_C Card Game
import java.io.*;

class Main {

   public static void main(String[] args) {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      int taro = 0;
      int hanako = 0;
      try {
         int n = Integer.parseInt(br.readLine());
         for (int i = 0; i < n; i++) {

            String[] cards = br.readLine().split(" ");
            if (cards[0].compareTo(cards[1]) > 0) {
               taro += 3;
            } else if (cards[0].compareTo(cards[1]) == 0) {
               taro++;
               hanako++;
            } else if (cards[0].compareTo(cards[1]) < 0) {
               hanako += 3;
            }
         }
         System.out.println(taro + " " + hanako);
      }
      catch (Exception e) {
         System.err.println(e);
      }
   }
}

Measured memory_bytes: 20228
#include<stdio.h>
int N,i,j,f=0;
char A[10][9]={
	"* = ****",//0
	"* =* ***",//1
	"* =** **",//2
	"* =*** *",//3
	"* =**** ",//4
	" *= ****",//5
	" *=* ***",//6
	" *=** **",//7
	" *=*** *",//8
	" *=**** ",//9
};
int main()
{
	for(;~scanf("%d",&N);)
	{
		if(f++)puts("");
		for(i=0;i<8;i++)
		{
			for(j=10000;j>0;j/=10)
				putchar(A[N/j%10][i]);
			if(i<8)puts("");
		}
	}
	return 0;
}

Measured memory_bytes: 588
#include<cstdio>
#include<iostream>
#include<string>

using namespace std;
typedef long long ll;
int n,c;

bool check(ll q){
	int cd[11];
	for(int i=0;i<n*2+1;i++){
		cd[i]=q%10;
		q/=10;
	}
	if(cd[n]!=c)return false;
	for(int i=0;i<n;i++){
		if(cd[i]!=cd[n*2-i])return false;
	}
	return true;
}

int main(void){
	scanf("%d%d",&n,&c);
	if(c<0){
		if(n==1)printf("11\n");
		else{
			string s;
			for(int i=0;i<n*2;i++)s+='9';
			cout << s << endl;
		}
		return 0;
	}
	
	ll q=0;
	for(int i=0;i<n*2+1;i++)q=q*10+9;
	while(1){
		if(check(q)){
			bool f=true;
			for(ll i=2;i*i<=q;i++){
				if(q%i==0)f=false;
				if(!f)break;
			}
			if(f){
				printf("%lld\n",q);
				return 0;
			}
		}
		q--;
	}
	return 0;
}

Measured memory_bytes: 1208
#include <algorithm>
#include <bitset>
#include <climits>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <vector>

#define MOD 1000000007
#define PI 3.14159265358979

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

using namespace std;

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

struct edge {
	int from, to, d, c;
	edge(int _from = 0, int _to = 0, int _d = 0, int _c = 0) {
		from = _from;
		to = _to;
		d = _d;
		c = _c;
	}
	bool operator<(const edge &rhs) const {
		return (d == rhs.d) ? (c < rhs.c) : (d < rhs.d);
	}
};

typedef vector< edge > edges;
typedef vector< edges > graph;

const int di[4] = {0, -1, 0, 1};
const int dj[4] = {-1, 0, 1, 0};
const int ci[5] = {0, 0, -1, 0, 1};
const int cj[5] = {0, -1, 0, 1, 0};
const ll LINF = LLONG_MAX / 2;
const int INF = INT_MAX / 2;

template < typename T >
bool chmin(T &x, const T &y) {
	if (x > y) {
		x = y;
		return true;
	}
	return false;
}
template < typename T >
bool chmax(T &x, const T &y) {
	if (x < y) {
		x = y;
		return true;
	}
	return false;
}

struct initializer {
	initializer() {
		cout << fixed << setprecision(11);
	}
};
initializer _____;

int N, M, K, T, Q;
int main() {
	ll N;
	cin >> N;
	ll ans = LINF;
	for (ll i = 1; i * i <= N; i++) {
		if (N % i == 0) {
			chmin(ans, i + (N / i) - 2);
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(void){

  int M, D;  cin >> M >> D;
  int ans = 0;
  for(int i = 1 ; i <= M ; i++){
      for(int j = 1 ; j <= D ; j++){

	int keep = j;
    int d1 = keep % 10;
    keep /= 10;
    int d10 = keep % 10;
	if(i == d1 * d10 && 2 <= d1 && 2 <= d10) ans++;

      }
  }

  cout << ans << endl;


  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include <algorithm>
#include<string>
using namespace std;
int main() {
    string s;
    cin>>s;
    if(s=="SUN")cout<<7<<endl;
    else if(s=="MON")cout<<6<<endl;
    else if(s=="TUE")cout<<5<<endl;
    else if(s=="WED")cout<<4<<endl;
    else if(s=="THU")cout<<3<<endl;
    else if(s=="FRI")cout<<2<<endl;
    else if(s=="SAT")cout<<1<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
template<class T> inline bool chmax(T &a, T b) { if (a<b) {a=b; return 1;} return 0;}
template<class T> inline bool chmin(T &a, T b) { if (b<a) {a=b; return 1;} return 0;}

const int INF = 1001001001;

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

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

int main(){
    #define int long long
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int n ,W; cin>>n>>W;
    if( n == 0 ){
    	cout << "0" << endl;
        return 0;
    }
    vector<int > w(n);
    vector<int > v(n);
    for(int i=0;i<n;i++)
        cin>> w[i] >> v[i] ;
    vector<vector<int > > dp(n,vector<int > (W+1));
    for(int i=w[0];i<=W;i++){
        dp[0][i] = v[0];
    }
    for(int i=1;i<n;i++){
        for(int j=1;j<=W;j++ ){
            dp[i][j] = dp[i-1][j];
            if( w[i]<=j ) dp[i][j] = max( dp[i][j] , v[i] + dp[i-1][j-w[i]] ) ;
        }
    }
    cout << dp[n-1][W] << endl;
    return 0;
	
}

Measured memory_bytes: 79488
#include <iostream>
#include <cstdio>
#include <iomanip>
using namespace std;

int main(){
	int n;
	while(1){
		cin >> n;
		if(n==0) break;
		int a[n+1][n+1];
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++) cin >> a[j][i];
			a[n][i] = 0;
			for(int j=0;j<n;j++) a[n][i] += a[j][i];
		}
		for(int i=0;i<=n;i++){
			a[i][n] = 0;
			for(int j=0;j<n;j++) a[i][n] += a[i][j];
		}
		for(int i=0;i<=n;i++){
			cout << right << setw(5) << a[0][i];
			for(int j=1;j<=n;j++) cout << right << setw(5) << a[j][i];
			cout << endl;
		}
	}
}

Measured memory_bytes: 1176
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <cmath>
#include <tuple>
#include <cstdio>
#include <bitset>
#include <sstream>
#include <iterator>
#include <numeric>
#include <map>
#include <cstring>
#include <set>

using namespace std;

//#define DEBUG_ //!!提出時にコメントアウト!!
#ifdef DEBUG_
	#define dump(x)  cerr << #x << " = " << (x) << endl;
#else
	#define dump(x)  ; //何もしない文
#endif

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SZ(x) ((int)(x).size()) //unsignedのサイズをint型に変換
#define pb push_back

//#define int long long

typedef long long LL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

template <typename T>
std::string printVector(const std::vector<T> &data)
{
    std::stringstream ss;
    std::ostream_iterator<T> out_it(ss, ", ");
    ss << "[";
    std::copy(data.begin(), data.end() - 1, out_it);
    ss << data.back() << "]";
    return ss.str();
}

const int MOD = 1e9+7;
const LL LINF = 1001002003004005006ll;
const int INF = 1001001001;

long long int gcd(long long int a, long long int b) {
    if (a < b)swap(a, b);
    while (b) {
        a %= b;
        swap(a, b);
    }
    return a;
}

signed main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N; cin>>N;
    vector<LL> A(N);
    vector<LL> logcd(N-2);
    REP(i,N) cin>>A[i];
    for(int i = 0; i+2 < N; i++)
    {
        LL a,b,c;
        a = A[i]; b = A[i+1]; c = A[i+2];
        logcd[i] = gcd(gcd(a,b),c);

    }
    LL minrec = LINF;
    int mindex;
    REP(i,N-2)
    {
        if(logcd[i] < minrec)
        {
            minrec = logcd[i];
            mindex = i;
        }
    }
    VI jogailist;
    for(int i = mindex-7; i <= mindex+7; i++)
    {
        if(0<= i && i <= N-1) jogailist.pb(i);
    }
    LL ans = 0;
    for(auto p : jogailist)
    {
        LL kouho = 0;
        dump(p)
        REP(i,N)
        {
            if(p != i) kouho = gcd(kouho,A[i]);
            dump(kouho)
        }
        if(kouho > ans) ans = kouho;
    }
    cout << ans << endl;



}

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

int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> vec(n, 0);
    for (int i=0; i<m; i++){
        int a,b;
        cin >> a >> b;
        vec.at((a-1))++;
        vec.at((b-1))++;
    }
    for (int i=0; i<n; i++){
        cout << vec.at(i) << endl;
    }
}

Measured memory_bytes: 256
/*Author: Gautam*/


#include<bits/stdc++.h>
#define FastIO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
#define MOD 1000000007
#define INF 1e10
#define ull unsigned long long int

/* TYPE DEFINITIONS */
typedef		long long int	ll;
typedef		vector<ll>		vi;
typedef		pair<ll,ll>	    pi;



/* Prime Checker!!! */
bool isPrime(ull n) 
{ 
    if (n <= 1)  return false; 
    if (n <= 3)  return true; 
    if (n%2 == 0 || n%3 == 0) return false; 
  
    for (ull i=5; i*i<=n; i=i+6) 
        if (n%i == 0 || n%(i+2) == 0) 
           return false; 
  
    return true; 
} 

/* MACROS */

#define  all(A)			(A).begin() , (A).end()
#define  rall(A)		(A).rbegin() , (A).rend()
#define  sz(A)			(int)(A).size()
#define  pb				push_back
#define  ppb			pop_back
#define  mp				make_pair
#define  ln(X)			(int)(X).length()
#define  square(X)		((X)*(X))
#define  cube(X)		((X)*(X)*(X))
#define  forn(i, n)  for (int i = 0; i < int(n); i++)
#define  forr(i, n)  for (int i = int(n - 1); i >= 0; i--)
#define  fora(i, a, b)  for (int i = int(a); i <= int(b); i++)
#define  forb(i, a, b)  for (int i = int(a); i >= int(b); i--)
#define  fore(it, a)	for(__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++) 
void solve()
{
    ll a,b;
    cin>>a>>b;
    ll c=b,d=a;
    vi v;
    while(d--)
    {
        v.pb(--b);
    }
    while(a--)
    {
        v.pb(c++);
    }
    sort(all(v));
    for(int i=1;i<v.size();i++)cout<<v[i]<<" ";
}   


int main()
{
	FastIO;
	ll t=1;
    //cin>>t;
    //double start_time = clock();
	while(t--)
    {
        solve();
    }
    //double end_time = clock();
   // printf( "\nTime = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);
}

Measured memory_bytes: 256
r, c = map(int, input().split())
sheet = [[0 for i in range (c)] for j in range(r)]

for i in range(r):
	sheet[i] = input().split()
	k = 0
	for j in range(c):
		k += int(sheet[i][j])
	sheet[i].append(k)
	
l=[0 for i in range (c+1)]
for j in range(c+1):
	for i in range(r):
		l[j] += int(sheet[i][j])
		#print(sheet[i][j])
sheet.append(l)

for i in range(r+1):
	for j in range(c+1):
		if j != c:
			print(sheet[i][j], end=' ')
		else:
			print(sheet[i][j], end='')
			print('')

Measured memory_bytes: 8628
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
import fractions
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    a,b = map(int,ipt().split())
    g = fractions.gcd(a,b)

    #素因数分解
    def factorization(n):
        d = dict()
        ni = n
        pn = 2
        t = 0
        while pn**2 <= n and ni > 1:
            if ni%pn == 0:
                t += 1
                ni //= pn
            else:
                if not t == 0:
                    d[pn] = t
                    t = 0
                if pn == 2:
                    pn = 3
                else:
                    pn += 2
        if t > 0:
            d[pn] = t
        if ni > 1:
            d[ni] = 1
        return d

    d = factorization(g)
    print(len(d.keys())+1)
    return

if __name__ == '__main__':
    main()


Measured memory_bytes: 61292
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
   int n;
   cin>>n;
   int arr[n],ar[n];

   for(int i=1;i<=n;i++)
   {
       cin>>arr[i];
   }

   for(int i=1;i<=n;i++)
   {
       ar[arr[i]] = i;


   }
   for(int i=1;i<=n;i++)
   {
      cout<<ar[i]<<" ";
   }


    return 0;
}







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

int main(){
	string s, t;
	cin >> s >> t;
	
	rep(i, s.size()){
		if(s == t){
			cout << "Yes" << endl;
			return 0;
		}

		s = s.back() + s.substr(0, s.size()-1);
	}
	cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 3624
n, m, c = map(int, input().split())
b = list(map(int, input().split()))
ans = 0
for i in range(n):
  a = list(map(int, input().split()))
  res = c
  for j in range(m):
    res += a[j] * b[j]
  if res > 0:
    ans += 1
print(ans)

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

int main(){
  int N,M; cin >> N >> M;
  int q[5][2];
  for(int i=0; i<M; i++){
    cin >> q[i][0] >> q[i][1];
  }
  
  int len=1;
  while(N--) len*=10;
  
  for(int i=len/10-(len/10==1?1:0); i<len; i++){
    string str=to_string(i);
    bool f=true;
    for(int j=0; j<M; j++){
      if(str[q[j][0]-1]-'0'!=q[j][1]) f=false;
    }
    if(f==true){
      cout << str << endl;
      return 0;
    }
  }
  cout << -1 << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string>

int main()
{
	int count;
	int b,f,r,v;
	int temp;
	int room[4][3][10];

	for(int i=0;i<4;i++){
		for(int l=0;l<3;l++){
			for(int o=0;o<10;o++){
				room[i][l][o] = 0;
			}
		}
	}
	
	//箇数を入力
	scanf("%d\n",&count);

	for(int i=0;i<count;i++){
		scanf("%d %d %d %d\n",&b,&f,&r,&v);
		room[b-1][f-1][r-1] = room[b-1][f-1][r-1] + v;
	}

	//result
	int tno=0;
	for(int i=0;i<3;i++){
		printf(" %d %d %d %d %d %d %d %d %d %d\n",room[tno][i][0],room[tno][i][1],room[tno][i][2],room[tno][i][3],room[tno][i][4],room[tno][i][5],room[tno][i][6],room[tno][i][7],room[tno][i][8],room[tno][i][9]);
	}
	printf("####################\n");
	tno=1;
	for(int i=0;i<3;i++){
		printf(" %d %d %d %d %d %d %d %d %d %d\n",room[tno][i][0],room[tno][i][1],room[tno][i][2],room[tno][i][3],room[tno][i][4],room[tno][i][5],room[tno][i][6],room[tno][i][7],room[tno][i][8],room[tno][i][9]);
	}
	printf("####################\n");
	tno=2;
	for(int i=0;i<3;i++){
		printf(" %d %d %d %d %d %d %d %d %d %d\n",room[tno][i][0],room[tno][i][1],room[tno][i][2],room[tno][i][3],room[tno][i][4],room[tno][i][5],room[tno][i][6],room[tno][i][7],room[tno][i][8],room[tno][i][9]);
	}
	printf("####################\n");
	tno=3;
	for(int i=0;i<3;i++){
		printf(" %d %d %d %d %d %d %d %d %d %d\n",room[tno][i][0],room[tno][i][1],room[tno][i][2],room[tno][i][3],room[tno][i][4],room[tno][i][5],room[tno][i][6],room[tno][i][7],room[tno][i][8],room[tno][i][9]);
	}

	return 0;
}




Measured memory_bytes: 2740
use std::io::Read;
fn main() {
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();
    let mut iter = buf.split_whitespace();
    let n: usize = iter.next().unwrap().parse().unwrap();
    let m: usize = iter.next().unwrap().parse().unwrap();

    let mut h = vec![0; m];

    for _ in 0..n {
        let k: usize = iter.next().unwrap().parse().unwrap();
        for _ in 0..k {
            let a: usize = iter.next().unwrap().parse().unwrap();
            h[a - 1] += 1;
        }
    }

    println!("{}", h.iter().filter(|&x| *x == n).count());
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
#define rep(i, c) for(int i = 0; i < (int)c; i++)
using namespace std;
int main()
{
    int N, K; cin >> N >> K;
    vector<int> X(N);
    rep(i, N) cin >> X[i];
    sort(X.begin(), X.end(), greater<int>());
    cout << accumulate(X.begin(), X.begin() + K, 0) << endl;
}

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

using namespace std;

const int max_n = 1011, inf = 1000111222;

long long mabs(long long x) {
    if (x < 0) {
        return -x;
    }
    return x;
}

int n;
long long x[max_n], y[max_n];
int f[2];

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> x[i] >> y[i];
        f[(((x[i] + y[i]) % 2) + 2) % 2] = 1;
    }
    if (f[0] + f[1] == 2) {
        cout << -1 << endl;
        return 0;
    }
    vector<long long> all;
    if (f[0]) {
        all.push_back(1);
    }
    for (int i = 33; i >= 0; --i) {
        all.push_back(1LL << i);
    }
    cout << all.size() << endl;
    for (long long x : all) {
        cout << x << " ";
    }
    cout << endl;
    if (f[0]) {
        all.erase(all.begin());
    }
    for (int i = 0; i < n; ++i) {
        long long sum = accumulate(all.begin(), all.end(), 0LL);
        if (f[0]) {
            cout << 'R';
            --x[i];
        }
        for (long long a : all) {
            sum -= a;
            if (mabs(x[i] - a) + mabs(y[i]) <= sum) {
                cout << 'R';
                x[i] -= a;
            } else if (mabs(x[i] + a) + mabs(y[i]) <= sum) {
                cout << 'L';
                x[i] += a;
            } else if (mabs(x[i]) + mabs(y[i] - a) <= sum) {
                cout << 'U';
                y[i] -= a;
            } else if (mabs(x[i]) + mabs(y[i] + a) <= sum) {
                cout << 'D';
                y[i] += a;
            } else {
                exit(228);
            }
        }
        cout << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES

#include <iostream>
#include <cstdio>
#include <memory>
#include <string>
#include <cstdlib>
#include <set>
#include <utility>
#include <vector>
#include <list>
#include <algorithm>
#include <regex>
#include <cmath>
#include <map>
#include <iterator>
#include <climits>
#include <numeric>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <queue>
#include <deque>
#include <stack>
#include <array>
#include <valarray>
#include <complex>
#include <random>
#include <functional>
#include <cassert>
#include <chrono>
#include <memory>

using namespace std;

#define int long long
//region TEMPLATE
////@formatter:off
#define double long double
typedef long long ll;
typedef unsigned long long ull;
template<typename T>void __read(T &a) { cin >> a; }
template<typename T, typename ... Args> void __read(T &a, Args &... args) { cin >> a;__read(args...);}
#define make(t, ...) t __VA_ARGS__; __read(__VA_ARGS__)
#define makev(a, n) VI a(n); FOR(n) cin >> a[i]
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define FORIT(p) for(auto it = p.begin(); it != p.end(); it++)
#define FOR(b) for(signed i = 0; i <(b); i++)
#define FORE(i, l, r) for(int i = (l); i < (r); i++)
#define NFOR(i, n) for(int i = (((int) n)-1); i >= 0; i--)
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
typedef pair<int, int> PII;
typedef pair<pair<int, int>, int> PPII;
constexpr ll M7 = 1000000007ll;
constexpr ll M9 = 1000000009ll;
constexpr ll MFFT = 998244353ll;
template<class T> void outv(T &a) { for (auto &x : a) cout << x << ' '; }
static mt19937 rnd(static_cast<unsigned>(chrono::steady_clock::now().time_since_epoch().count())); // NOLINT(cert-err58-cpp)
auto __fast_io__ = (ios_base::sync_with_stdio(false), cin.tie(nullptr)); // NOLINT(cert-err58-cpp,cppcoreguidelines-interfaces-global-init)
////@formatter:on
//endregion



int32_t main() {
    make(string, s, t);
    VVI dp(s.length() + 1, VI(t.length() + 1, -1));
    VVI pr_i = dp;
    VVI pr_j = dp;
    dp[0][0] = 0;
    for (int i = 0; i <= s.length(); ++i) {
        for (int j = 0; j <= t.length(); ++j) {
            if (i != s.length() && dp[i + 1][j] < dp[i][j]) {
                dp[i + 1][j] = dp[i][j];
                pr_i[i + 1][j] = i;
                pr_j[i + 1][j] = j;
            }
            if (j != t.length() && dp[i][j + 1] < dp[i][j]) {
                dp[i][j + 1] = dp[i][j];
                pr_i[i][j + 1] = i;
                pr_j[i][j + 1] = j;
            }
            if (i != s.length() && j != t.length() && s[i] == t[j] && dp[i + 1][j + 1] <= dp[i][j]) {
                dp[i + 1][j + 1] = dp[i][j] + 1;
                pr_i[i + 1][j + 1] = i;
                pr_j[i + 1][j + 1] = j;
            }
        }
    }
    string ans(dp.back().back(), '\0');
    int i = s.length(), j = t.length();
    while (i > 0 || j > 0) {
        int pi = pr_i[i][j];
        int pj = pr_j[i][j];
        if (pi != i && pj != j) {
            ans[dp[pi][pj]] = s[pi];
        }
        i = pi;
        j = pj;
    }
    cout << ans;

    return 0;
}

Measured memory_bytes: 211584
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
#include <complex>
using namespace std;

typedef long long ll;
typedef uint64_t ull;
typedef pair<int, int> P;
constexpr double PI = 3.1415926535897932;   // acos(-1)
constexpr double EPS = 1e-9;
constexpr int INF = 1001001001;
constexpr int mod = 1000000007;
// constexpr int mod = 998244353;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)

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

    int k, a, b;
    cin >> k >> a >> b;
    for(int i = a; i <= b; ++i){
        if(i % k == 0){
            cout << "OK\n";
            return 0;
        }
    }
    cout << "NG\n";
}

Measured memory_bytes: 3640
#include<iostream>
using namespace std;
int main(){
	char c;
	cin>>c;
	if(c=='A')
		cout<<'T';
	else if(c=='T')
		cout<<'A';
	else if(c=='C')
		cout<<'G';
	else if(c=='G')
		cout<<'C';
	return 0;
}


Measured memory_bytes: 256
gets.to_i
arr = gets.split.map(&:to_i)

puts arr.join("\s")

1.step(arr.size - 1) do |i|
  v = arr[i]
  j = i - 1
  while j >= 0 && arr[j] > v
    arr[j + 1] = arr[j]
    j -= 1
  end
  arr[j + 1] = v

  puts arr.join("\s")
end



Measured memory_bytes: 6900
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
	ll n,k,q;
	cin>>n>>k>>q;
	vector<int> a(n,0);
	for(int i = 0 ; i < q ; i++)
	{
		int k; cin>>k;
		a[k-1]++;
	}
	for(int i = 0; i < n ; i++)
	{
		a[i]-=q;
		a[i]+=k;
		if(a[i]>0)
			cout<<"Yes\n";
		else
			cout<<"No\n";
	}
	return 0;
}

Measured memory_bytes: 1024
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <climits>

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

template<typename T1, typename T2>
inline void chmin(T1 &a, T2 b) { if (a > b) a = b; }

template<typename T1, typename T2>
inline void chmax(T1 &a, T2 b) { if (a < b) a = b; }

//改造
typedef long long int ll;
using namespace std;
#define INF (1 << 30) - 1
#define INFl (ll)5e15
#define DEBUG 0 //デバッグする時1にしてね
#define dump(x)  cerr << #x << " = " << (x) << endl
#define MOD 1000000007


//ここから編集する
class Solve {
public:
    int N, M;
    vector<vector<int>> G;
    vector<set<int>> rG;
    int root = -1;

    void input() {
        cin >> N >> M;
        G.resize(N);
        rG.resize(N);
        rep(i, 0, N + M - 1) {
            int a, b;
            cin >> a >> b;
            a--, b--;
            G[a].push_back(b);
            rG[b].insert(a);
        }


        for (int i = 0; i < N; ++i) {
            if (rG[i].size() == 0) root = i;
        }
    }


    void solve() {
        input();
        vector<int> tree(N, -1);

        queue<int> que;

        que.push(root);
        while (!que.empty()) {
            int top = que.front();
            que.pop();

            int v = top;

            for (auto nv : G[v]) {
//                que.push(nv);
//                tree[nv] = v;
                if (rG[nv].size() == 1) {
                    que.push(nv);
                    tree[nv] = v;
                } else if (rG[nv].size() == 0) {
                    tree[nv] = v;
                } else {
                    rG[nv].erase(v);
                }
            }
        }


        for (int i = 0; i < N; ++i) {
            cout << tree[i] + 1 << endl;
        }

    }
};


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);

    Solve().solve();


    return 0;
}


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

#define MAX 100000

int main() {
	long long N, M;
	priority_queue<long long> A;
	priority_queue<pair<long long, long long>> C;
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		int a;
		cin >> a;
		A.push(-a);
	}
	for (int i = 0; i < M; i++) {
		int b, c;
		cin >> b >> c;
		C.push(make_pair(c, b));
	}
	while (!C.empty()) {
		auto c = C.top();
		C.pop();
		for (int i = 0; i < c.second; i++) {
			if (-A.top() >= c.first) {
				while (!C.empty()) {
					C.pop();
				}
				break;
			}
			A.pop();
			A.push(-c.first);
		}
	}
	long long ans = 0;
	while (!A.empty()) {
		ans += -A.top();
		A.pop();
	}
	cout << ans << endl;
	return 0;
}


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

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  string s[3];
  cin >> s[0] >> s[1] >> s[2];
  cout << s[0][0] << s[1][1] << s[2][2] << endl;
  return 0;
}


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

using namespace std;

int main()
{
    string n;
    cin >> n;
    for(int i = 0; i < n.size(); ++i){
        if(n[i] == '1') cout << '9';
        else if(n[i] == '9') cout << '1';
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vin=vector<int>;
using vll=vector<long long>;
using vvin=vector<vector<int>>;
using vvll=vector<vector<long long>>;
using vstr=vector<string>;
using vvstr=vector<vector<string>>;
using vch=vector<char>;
using vvch=vector<vector<char>>;
using vbo=vector<bool>;
using vvbo=vector<vector<bool>>;
using vpii=vector<pair<int,int>>;
using pqsin=priority_queue<int,vector<int>,greater<int>>;
#define mp make_pair
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep2(i,s,n) for(int i=(s);i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define decp(n) cout<<fixed<<setprecision((int)n)
#define _GLIBCXX_DEBUG
const int inf=1e9+7;

int main(){
    int n;cin>>n;
    vin x(n),y(n),h(n);
    rep(i,n)cin>>x[i]>>y[i]>>h[i];
    int tmp;
    bool can;
    rep(i,101)rep(j,101){
        rep(k,n){
            if(h[k]>0){
                tmp=h[k]+abs(x[k]-i)+abs(y[k]-j);
                break;
            }
        }
        can=true;
        rep(k,n){
            if(h[k]!=max(tmp-abs(x[k]-i)-abs(y[k]-j),0)){
                can=false;
                break;
            }
        }
        if(can){
            cout<<i<<" "<<j<<" "<<tmp<<endl;
            return 0;
        }
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <iomanip>
using namespace std;


int main() {

    ios::sync_with_stdio(false);
    cin.tie(0);

    int a, b, c, x, y;
    cin >> a >> b >> c >> x >> y;

    long long res = (x*a + y*b);
    for (int ab=0; ab <= (2*(x+y)); ab+=2) {

        long long ac = ab / 2;
        long long bc = ab / 2;

        long long cost = ab*c;

        cost += (max(x - ac, 0ll) * a);
        cost += (max(y - bc, 0ll) * b);

        res = min(res, cost);
    }

    cout << res << endl;
    return 0;
}


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

int main(void) {
	int X[3];
	int K;

	for (int i = 0; i < 3; ++i)
		cin >> X[i];
	cin >> K;

	sort(X, X + 3);
	int ans = X[2];
	while (K > 0) {
		ans *= 2;
		--K;
	}
	ans += X[0] + X[1];

	cout << ans << '\n';
	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<stdint.h>
#include<inttypes.h>
#include<string.h>

typedef int32_t i32;

#define POS(l, r, x) ((((x) & 1)* (n + 1) + (l)) * (n + 1) + (r))

i32 max (i32 a, i32 b) {
  return a > b ? a : b;
}

void run (void) {
  char s[301];
  scanf ("%s", s);
  i32 n = strlen (s);
  i32 k;
  scanf ("%" SCNi32, &k);
  i32 *dp = (i32 *) calloc ((n + 1) * (n + 1) * 2, sizeof (i32));
  for (i32 x = 0; x <= k; ++x) {
    for (i32 l = 0; l < n; ++l) {
      dp[POS(l, l + 1, x)] = 1;
    }
    for (i32 len = 2; len <= n; ++len) {
      for (i32 l = 0; l < n + 1 - len; ++l) {
        i32 r = l + len;
        i32 local = max(dp[POS(l, r - 1, x)], dp[POS(l + 1, r, x)]);
        if (s[l] == s[r - 1]) {
          local = dp[POS(l + 1, r - 1, x)] + 2;
        } else if (x > 0) {
          local = max (local, dp[POS(l + 1, r - 1, x - 1)] + 2);
        }
        dp[POS(l, r, x)] = local;
      }
    }
  }
  printf ("%" PRIi32 "\n", dp[POS(0, n, k)]);
}

int main (void) {
  run();
  return 0;
}


Measured memory_bytes: 1024
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define X first
#define Y second
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const double pi = acos(-1.0);
int main(){
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int a, b;
    cin >> a >> b;
    for(int i = 1; i <= 1000; i++){
        int rate_1 = (i*0.08) / 1;
        int rate_2 = (i*0.1) / 1;
        if(rate_1 == a and rate_2 == b){
            cout << i;
            return 0;
        }
    }
    cout << -1;
    return 0;
}

Measured memory_bytes: 256
($a, $b, $c, $x) = <>;
$ans = 0;
for ($i = 0; $i <= $a; $i++) {
  for ($j = 0; $j <= $b; $j++) {
    for ($k = 0; $k <= $c; $k++) {
      $ans++ if 500*$i+100*$j+50*$k==$x;
    }
  }
}
print $ans

Measured memory_bytes: 4644
n = int(input())
a = list(map(int, input().split()))
a = [a[i] - (i + 1) for i in range(len(a))]
a.sort()

median = a[len(a) // 2]
cnt = 0
for i in range(len(a)):
    cnt += abs(a[i] - median)

print(cnt)


Measured memory_bytes: 99668
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#define abdelrahman010 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef long long ll;
using namespace std;
const int N = 1e5 + 5;
int main() {
    abdelrahman010
    multiset<int> st;
    int n , m , a[N];
    pair<int , int> b[N];
    cin >> n >> m;
    for(int i = 0;i < n;i++)
        cin >> a[i] , st.insert(a[i]);
    for(int i = 0;i < m;i++)
        cin >> b[i].second >> b[i].first;
    sort(b , b + m , greater<>());
    for(int i = 0;i < m;i++) {
        while(*st.begin() < b[i].first && b[i].second) {
            b[i].second--;
            st.erase(st.begin());
            st.insert(b[i].first);
        }
    }
    ll ans = 0;
    for(auto &i : st)
        ans += i;
    cout << ans;
    return 0;
}

Measured memory_bytes: 9488
#pragma GCC optimize "-O3"
#include <bits/stdc++.h>
using namespace std;
#define lo long
const long long lmax=1999999999;
const long long lmx=1999999999999999999;
long long n,W,ans;
vector<long long>dp(100003,lmx);
vector<long long>dpp(100003,lmx);
long long w[100003];
long long v[100003];
int main(){std::ios::sync_with_stdio(false);
cin>>n>>W;
for(long long i=1;i<=n;i++){
	cin>>w[i]>>v[i];
}

dp[0]=dpp[0]=0;
for(long long i=1;i<=n;i++){
	dpp=dp;
	for(long long j=0;j<=100003;j++){
		if(j+v[i]>100000)break;
		if(dp[j]!=lmx&&dp[j]+w[i]<=W){
			dpp[j+v[i]]=min(dp[j]+w[i],dp[j+v[i]]);
		}
	}
	dp=dpp;
}
for(int j=100000;j>=0;j--){
	if(dp[j]!=lmx){
		cout<<j<<endl;
		return 0;
	}
}
}
/*

                   *         *
                  * *       * *
                 *   *     *   *
                *     *   *     *
               *       * *       *
               *        *        *
                *               *
                 *             *
                  *           *
                   *         *
                    *       *
                     *     *
                      *   *
                       * *
                        *



*/





Measured memory_bytes: 1792
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
	
		Scanner scanner = new Scanner(System.in);
		if(scanner.hasNext()) {
			int x = scanner.nextInt();
			if(x==3||x==5||x==7) {
				System.out.println("YES");
			}else {
				System.out.println("NO");
			}
			scanner.close();
		}
	}
	
}

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

#define FOR(i,a,b) for (int i = a; i < b; ++i)
#define REP(i,n) FOR(i,0,n)

char S[4];
int count[3] = {0};

int main() {
  scanf("%s", S);
  REP(i,3) count[S[i] - 'a'] += 1;
  REP(i,3) {
    if (count[i] != 1) {
      printf("No\n");
      return 0;
    }
  }

  printf("Yes\n");
  return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    Map<String, Integer> map = new HashMap<>();
    for (int i = 0; i < N; i++) {
      String s = sc.next();
      map.put(s, map.getOrDefault(s, 0)+1);
    }
    int M = sc.nextInt();
    for (int i = 0; i < M; i++) {
      String t = sc.next();
      map.put(t, map.getOrDefault(t, 0)-1);
    }
    
    int max = 0;
    for (int value : map.values()) {
      if (value > max) {
        max = value;
      }
    }
    
    System.out.println(max);
  }
}

Measured memory_bytes: 22996
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(Sd, T):
    L = len(T)
    for i in range(len(Sd)-L, -1, -1):
        for j in range(L):
            if Sd[i+j] != '?' and Sd[i+j] != T[j]:
                break
        else:
            k = i
            break
    else:
        return 'UNRESTORABLE'

    S = [c for c in Sd]

    for i in range(len(S)):
        if S[i] == '?':
            S[i] = 'a'

    for i in range(L):
        S[k+i] = T[i]
    
    return ''.join(S)

def main():
    Sd = read_str()
    T = read_str()
    print(slv(Sd, T))


if __name__ == '__main__':
    main()


Measured memory_bytes: 5448
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

#include <vector>
#include <stdio.h>
#include <iostream>
#include <unordered_set>
#include <algorithm>
#include <bitset>
#include <set>
#include <map>
#include <random>
#include <time.h>
#include <cassert>

#define prev askdnsajd
#define rank asasdmdnasd
#define next lsjndajbs
#define hash asmdklansd
#define index asdklnas
#define right sld
#define left sldl
using namespace std;

typedef long long ll;
typedef long double dbl;

template<class T>
void print(vector<T> s){
    for (T x : s)
        cout << x << " ";
    cout << endl;
}

void solve(){

}

int main(){
    srand(17);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("a.in", "r", stdin);
    int n;
    cin >> n;
    vector<int> s(n);
    for (int i = 0; i < n; i++)
        cin >> s[i];
    sort(s.begin(), s.end());
   // cout << s[n / 2] << endl;
    cout << s[n / 2] - s[n / 2 - 1] << endl;
}

Measured memory_bytes: 640
n = int(input())
a = list(map(int, input().split()))
a.sort()
for ind, i in enumerate(a):
    if n%2==0 and i!=ind//2*2+1:
        print(0)
        exit()
    if n%2==1 and i!=(ind+1)//2*2:
        print(0)
        exit()
print(pow(2, n//2, 10**9+7))

Measured memory_bytes: 14008
#include<bits/stdc++.h>
#define rep(i,f,n) for(ll i=(f); (i) < (n); i++)
#define repe(i,f,n) for(ll i=(f); (i) <= (n); i++)
using namespace std;
using ll = long long;
#define MOD (ll)1000000007
#define PI 3.14159265359
#define debug(x) cout<<#x<<" :: "<<x<<"\n";
#define debug2(x,y) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\n";
#define debug3(x,y,z) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\t"<<#z<<" :: "<<z<<"\n";
#define P pair<ll, ll>
#define dvec vector<vector<ll>>
//printf("%.10f\n")
//cout << fixed << setprecision(10);
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;}
ll INF = 1e+18;
int iINF = 1e9;

int main()
{
  int N, M; cin >> N >> M;
  dvec G(N);
  rep(i, 0, M){
    int a, b; cin >> a >> b;
    --a, --b;
    G[a].push_back(b);
    G[b].push_back(a);
  }

  vector<int> dist(N, -1);
  queue<int> q;
  q.push(0);
  dist[0] = 0;

  while(!q.empty()){
    int node = q.front();
    q.pop();
    for(int next: G[node]){
      if(dist[next] == -1) dist[next] = node, q.push(next);
    }
  }

  cout << "Yes" << endl;
  rep(i, 1, N) cout << dist[i] + 1 << endl;
}



Measured memory_bytes: 12420
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;


int main() {
	int N, Y;
	cin >> N >> Y;
	for (int i = 0; i <= N; i++) {
		for (int j = 0; j <= N - i; j++) {
			if ((Y - 10000 * i - 5000 * j) / 1000 == N - i - j&&N-i-j>=0) {
				cout << i << " " << j << " " << N - i - j << endl;
				return 0;

			}

		}
	}
	cout << -1 << " " << -1 << " " << -1 << endl;
}


Measured memory_bytes: 256
n,a,b,c,d = map(int,input().split())

res = 0
r = b-a
for k in range(1,n):
    s1 = k*c - d *(n-1-k)
    t1 = k*c - c *(n-1-k)
    if s1 <= r and r <= t1:
        res = 1
        break
    
    s1 = k*d - d *(n-1-k)
    t1 = k*d - c *(n-1-k)
    if s1 <= r and r <= t1:
        res = 1
        break

if res == 1:
    print("YES")
else:
    print("NO")

Measured memory_bytes: 40876
"""

問題文:

制約:

解読:
- 2, 5はO(n)で求められるとのこと
  - 最後の桁がpで割り切れるかどうかのみで判定可能なため
  - solve1で、cntをi + 1でカウントしている理由:
    - 対象となる部分文字列は連続した部分文字列
    - iをインクリメントしながらカウント
    - i番目の数字を含む部分文字列のみカウントすればよい -> (i + 1)個
"""
n, p = map(int, input().split())
s = list(map(int, list(input())))
u = [0 for _ in range(n + 1)]

d = 1
for i in range(n):
    u[n-(i+1)] = (u[n-i] + s[n-i-1] * d) % p
    d = 10 * d % p


def solve(u, s, p):
    if 2 == p or 5 == p:
        return solve1(s, p)
    else:
        return solve2(u, p)


def solve1(s, p):
    ans = 0
    for i in range(n):
        if s[i] % p == 0:
            ans += i + 1
    return ans


def solve2(u, p):
    ans = 0
    cnt = [0 for _ in range(p)]
    for i in range(n + 1):
        cnt[u[i]] += 1
    for i in range(p):
        p = cnt[i]
        ans += (p * (p-1)) // 2
    return ans


print(solve(u, s, p))


Measured memory_bytes: 12412
#include<bits/stdc++.h>
using namespace std;
struct cube{
  int x,y,z;
  cube(){}
  cube(int x,int y,int z):x(x),y(y),z(z){}
};
#define MAX 3000
bool used[MAX];
int c[MAX][MAX];
vector<cube> vc;
vector<int> vi;
vector<vector<int> > G;
bool dfs(int v,int p){
  bool f=false;
  if(used[v]) return true;
  vi.push_back(v);used[v]=1;
  for(int i=0;i<G[v].size();i++) {
    if(i&&!~p) reverse(vi.begin(),vi.end());
    if(G[v][i]!=p) f|=dfs(G[v][i],v);
  }
  return f;
}
int main(){
  int n,k,s,i,j,l,t;
  while(cin>>n>>k>>s,n||k||s){
    int ans=-1;
    memset(c,0,sizeof(c));
    G.clear();G.resize(n);
    vc.clear();vc.resize(n);
    for(i=0;i<n;i++) cin>>vc[i].x>>vc[i].y>>vc[i].z;
    for(i=0;i<n;i++){
      for(j=i+1;j<n;j++){
        int xx=s-abs(vc[i].x-vc[j].x),
          yy=s-abs(vc[i].y-vc[j].y),
          zz=s-abs(vc[i].z-vc[j].z);
        if(xx>0&&yy>0&&zz>0){
          G[i].push_back(j);
          G[j].push_back(i);
          c[i][j]=c[j][i]=(xx*yy+yy*zz+zz*xx)*2;
        }
      }
    }
    memset(used,0,sizeof(used));
    for(i=0;i<n;i++){
      if(used[i]) continue;
      vi.clear();
      bool f=dfs(i,-1);
      if(vi.size()<k) continue;
      t=0;
      if(f){
        if(vi.size()==k){
          for(j=0;j<k;j++) t+=c[vi[j]][vi[(j+1)%k]];
          ans=max(ans,t);
        }else{
          for(j=0;j<k-1;j++) t+=c[vi[j]][vi[j+1]];
          ans=max(ans,t);
          int si=vi.size();
          for(j=0;j<si;j++){
            t+=c[vi[(k-1+j)%si]][vi[(k+j)%si]]-c[vi[j%si]][vi[(j+1)%si]];
            ans=max(ans,t);
          } 
        }
      }else{
        for(j=0;j<k-1;j++) t+=c[vi[j]][vi[j+1]];
        ans=max(ans,t);
        for(j=0;j<vi.size()-k;j++){
          t+=c[vi[k-1+j]][vi[k+j]]-c[vi[j]][vi[j+1]];
          ans=max(ans,t);
        } 
      }
    }
    if(~ans) cout << s*s*6*k-ans << endl;
    else cout << -1 << endl;
  }
  return 0;
}

Measured memory_bytes: 38288
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

const long long LINF = 1LL << 60;

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

  vector<long long> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  vector<long long> sum(n + 10, 0);
  for (int i = 0; i < n; i++) {
    sum[i + 1] += sum[i] + a[i];
  }

  // dp[l][r] := 区間[l, r)にいるスライムを1体にするときのコストの総和の最小値
  vector<vector<long long>> dp(n + 1, vector<long long>(n + 1, 0));

  for (int wid = 2; wid <= n; wid++) {
    for (int l = 0; l + wid <= n; l++) {
      int r = l + wid;
      dp[l][r] = LINF;
      for (int mid = l + 1; mid < r; mid++) {
        long long cost = sum[r] - sum[l];
        dp[l][r] = min(dp[l][r], dp[l][mid] + dp[mid][r] + cost);
      }
    }
  }
  cout << dp[0][n] << endl;

  return 0;
}

Measured memory_bytes: 1536
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int tu[55][55];
int dd[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
struct node{
    int x,y,z;
    bool operator<(const node k)const{
        return z<k.z;
    }
};
priority_queue<node>q;
int n,w,d;
bool check(int a,int b)
{
    if(a>0&&a<=w&&b>0&&b<=d)return true;
    return false;
}
int main()
{

    cin>>w>>d>>n;
    for(int i=1;i<=w;i++)
        for(int j=1;j<=d;j++)tu[i][j]=1e5;
    while(n--)
    {
        int x,y,h;
        cin>>x>>y>>h;
        tu[x][y]=h;
        q.push(node{x,y,h});
    }
    int ok=1;
    while(!q.empty())
    {
        node p=q.top();q.pop();
        for(int i=0;i<4;i++)
        {
            int nx=p.x+dd[i][0];
            int ny=p.y+dd[i][1];
            if(tu[nx][ny]==100000&&check(nx,ny)) tu[nx][ny]=p.z-1,q.push(node{nx,ny,p.z-1});
            else if(check(nx,ny))
            {
                if(abs(tu[p.x][p.y]-tu[nx][ny])>=2) {ok=0;break;}
            }
        }
        if(!ok)break;
    }
    if(!ok){cout<<"No\n";return 0;}
    int ans=0;
    for(int i=1;i<=w;i++)
    {
        for(int j=1;j<=d;j++) ans+=tu[i][j];
    }
    cout<<ans<<endl;
    return 0;
}



Measured memory_bytes: 3164
#include <stdio.h>
int main(){

  int W,H,x,y,r;
  scanf("%d %d %d %d %d",&W,&H,&x,&y,&r);
  
  if(x >= r && y >= r && x + r <= W && y + r <= H){
    printf("Yes\n");
    
  }else{
    printf("No\n");
  }
  return 0;
}

Measured memory_bytes: 1800
<?php
  list($n) = explode(" ", trim(fgets(STDIN)));

  $a = explode(" ", trim(fgets(STDIN)));

  $cnt = [];
  $cand = [];
  for($i=0; $i<$n; $i++){
    if(!isset($cnt[$a[$i]])) $cnt[$a[$i]]=0;
    if($cnt[$a[$i]] == 1){
      $cand[] = $a[$i];
      $cnt[$a[$i]] = 0;
    }else{
      $cnt[$a[$i]] = 1;
    }
  }

  if(count($cand) < 2){
    echo "0";
    exit;
  }

  rsort($cand);
  echo $cand[0]*$cand[1];

Measured memory_bytes: 29120
import java.util.Scanner;

//Millennium
public class Main{

	void run(){
		Scanner sc = new Scanner(System.in);
		int[] d = {0, 20, 19, 20, 19, 20, 19, 20, 19, 20, 19};
		int T = sc.nextInt();
		while(T--!=0){
			int Y = sc.nextInt(), M = sc.nextInt(), D = sc.nextInt();
			int res = 0;
			while(!(Y==1000&&M==1&&D==1)){
				if(Y%3==0&&D==20 || Y%3!=0&&D==d[M]){
					M++; D=1;
				}
				else D++;
				if(M==11){
					Y++; M=1;
				}
				res++;
			}
			System.out.println(res);
		}
	}
	
	public static void main(String[] args) {
		new Main().run();
	}
}

Measured memory_bytes: 12000