akhauriyash/Code-Regression huggingface dataset:
S = input()
K = int(input())
N = len(S)

al = [chr(ord('a') + i) for i in range(26)]
tmp_al = []
if K==1:
    for s in al:
        if s in S:
            print(s)
            exit()

for s in al:
    if s in S:
        if len(tmp_al) == 3:
            break
        if N - S.rfind(s) >= K:
            tmp_al.append(s)
            break
        else:
            if N - S.find(s) >= K:
                tmp_al.append(s)
                break
            else:
                tmp_al.append(s)
                continue

count = [[] for _ in range(len(tmp_al))]
for i in range(len(tmp_al)):
    for k in range(N):
        if S[k] == tmp_al[i]:
            count[i].append(k)
ans_list = []
ans_list.append(tmp_al[0])
for i in count[0]:
    cnt = 1
    while (i + cnt <= N):
        if cnt == 7:
            break
        ans_list.append(S[i:i+cnt])
        cnt += 1

ans_list = list(set(ans_list))

if len(ans_list) < K:
    for i in count[1]:
        cnt = 1
        while (i + cnt <= N):
            if cnt == 7:
                break
            ans_list.append(S[i:i+cnt])
            cnt += 1
ans_list = list(set(ans_list))

if len(ans_list) < K:
    for i in count[2]:
        cnt = 1
        while i + cnt <= N:
            ans_list.append(S[i:i+cnt])
            cnt += 1
ans_list = list(set(ans_list))


ans_list.sort()
##print(ans_list)
print(ans_list[K-1])

Measured memory_bytes: 4972
#include <cstdio>
#include <iostream>
#include <cassert>
#include <algorithm>    
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <cstring>
#include <cmath>
#include <bitset>
#define mk make_pair
#define eb emplace_back
#define eps 1e-8
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
// #define int long long
using namespace std;

typedef long double ld;
typedef unsigned int ui;
typedef pair<int,int> pii;
typedef unsigned long long ull; 
typedef vector<int> vii;
typedef vector<long double> vd;
const int inf = 1e9;
const int M = 1e9 + 7;
//__int128


signed main()
{
  ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  int n;
  string s;
  cin >> n >> s;
  std::vector<int> a(26, 1);
  for(int i = 0; i < n; ++i) {
  	a[s[i] - 'a']++;
  }
  long long res = 1;
 	for(int i = 0; i < 26; ++i) {
 		res = (res * a[i]) % M;
 	}
 	res = (res - 1 + M) % M;
 	cout << res << endl;
	return 0;
}

Measured memory_bytes: 512
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<string>
#include<map>
#include<set>
#include<tuple>
#include<cmath>
#include<iomanip>
#include <stdio.h>


using namespace std;
typedef long long ll;
typedef vector<ll> v;
typedef vector<vector<ll>> vv;


#define MOD 1000000007
#define INF 1001001001
#define MIN -1001001001
#define rep(i,k,N) for(ll i=k;i<N;i++)
#define MP make_pair
#define MT make_tuple //tie,make_tuple は別物
#define PB push_back
#define PF push_front
#define all(x) (x).begin(),(x).end()


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


int main(){
    ll N;
    cin>>N;
    map<pair<ll,ll>,ll> grid;

    rep(i,0,N){
        string S;
        cin>>S;
        ll n2 = 0, n5 = 0;
        rep(j,0,S.size()){
            if(S[j] == '.'){
                n2 = -ll(S.size()-j-1);
                n5 = -ll(S.size()-j-1);
                //cout<<n2<<endl;
                S.erase(j,1);
                break;
            }
        }
        ll now = 0;
        ll n10 = 1;
        rep(j,0,S.size()){
            now += n10 * ll(S[S.size()-1-j] -'0');
            n10*=10;
        }
        while(now%2 == 0){
            now/=2;
            n2++;
        }
        while(now%5 == 0){
            now/=5;
            n5++;
        }
        grid[MP(n2,n5)]++;
        //cout<<n2<<" "<<n5<<endl;
    }


    ll ans = 0;
    rep(i,-30,30)rep(j,-30,30){
        rep(i2,-i,30)rep(j2,-j,30){
            if(i==i2 && j== j2)continue;
            ans += grid[MP(i,j)] * grid[MP(i2,j2)];
        }
    }
    ans/=2;
    rep(i,0,30)rep(j,0,30){
        ans += grid[MP(i,j)] * (grid[MP(i,j)]-1)/2;
    }
    cout<<ans;
    return 0;
}

Measured memory_bytes: 3780
#include <bits/stdc++.h>
#define ll long long
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
using P = pair <int, int>;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
const long long INF = 1LL << 60;
const int mod = 1000000007;

int main() {
    string s;
    cin >> s;
    int k;
    cin>>k;
    if(k<=s.size()){
    bool ok = true;
    rep(i,k){
        if(s[i]!='1') ok = false;
    }
    if(ok){
        cout << 1 << endl;
        return 0;
    }
    else{
        rep(i,k){
            if(s[i]!='1'){
                cout << s[i] <<endl;
                return 0;
            }
        }
    }
    }
    else{
        rep(i,s.size()){
            if(s[i]!='1') {
                cout << s[i] <<endl;
                return 0;
            }
        }
        cout << 1 <<endl;
    }

}

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

int main(){
   
  int number ;
  cin>>number ; 
  bool diti = false ; 
  
  if(number<10){
    cout<<"Yes"<<endl;
  }else{
  for(int x =1 ;x<10;x++){
     for(int y=1;y<10;y++){
       if(x*y==number){
         diti = true ;
         break;
       }
     }
  }
  if(diti)
     cout<<"Yes"<<endl; 
  else
    cout<<"No"<<endl; 
}
  return 0;
  
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string str;
    cin >> str;
    if(str[2] == str[3] && str[4] == str[5])
        cout << "Yes" << endl;
    else
        cout << "No" << endl;

}


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

vector<long long> solve(vector<long long> light){
    long long n = light.size();
    vector<long long> table(n, 0);
    for(long long i = 0; i < n; i++){
        long long start = max(0ll, i - light[i]);
        long long goal = min(n-1, i + light[i]);
        table[start]++;
        if(goal+1 < n) table[goal+1]--;
    }

    for(long long i = 0; i < n; i++){
        if(i > 0) table[i] += table[i-1];
    }
    return table;
}
int main(){
    long long n, k;
    cin >> n >> k;
    vector<long long> light(n);

    vector<long long> light_max(n, n);

    for(long long i = 0; i < n; i++){
        cin >> light[i];
    }

    for(long long i = 0; i < k; i++){
        light = solve(light);
        if(light == light_max){
            for(long long j = 0; j < n; j++){
                printf("%lld ", light_max[j]);
            }
            printf("\n");
            return 0;
        }
    }

    for(long long i = 0; i < n; i++){
        printf("%lld ", light[i]);
    }
    printf("\n");
    return 0;
}

Measured memory_bytes: 9528
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int k;
    string s, ans;
    cin >> k >> s;
    if(int(s.size()) <= k){
        ans = s;
    } else {
        ans = s.substr(0, k) + "...";
    }
    cout << ans << endl;
    return 0;
}

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

const int maxn = 205000;

int n,m;
int a[maxn];
vector <int> g[maxn];
int um[maxn][2];
int arr[maxn];

void read(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
	char ch = getchar();while(ch != 'A' && ch !='B')ch=getchar();
	a[i]=ch-'A';
    }
    for(int i=1;i<=m;i++){
	int u,v; scanf("%d%d",&u,&v);
	g[u].push_back(v); g[v].push_back(u);
	um[u][a[v]]++; um[v][a[u]]++;
    }
}

queue <int>q;
void work(){
    for(int i=1;i<=n;i++){
	if(um[i][0] == 0 || um[i][1] == 0) q.push(i);
    }
    while(!q.empty()){
	int k = q.front();q.pop();
	if(arr[k] == 1) continue;
	arr[k] = 1;
	for(int i=0;i<g[k].size();i++){
	    um[g[k][i]][a[k]]--;
	    if(um[g[k][i]][a[k]] == 0&&!arr[g[k][i]]){
		q.push(g[k][i]);
	    }
	}
    }
    for(int i=1;i<=n;i++){
	if(!arr[i]){puts("Yes");return;}
    }
    puts("No");
}

int main(){
    read();
    work();
    return 0;
}


Measured memory_bytes: 13952
#include<bits/stdc++.h>
#define MAX 110
#define inf 1<<29
#define linf 1e16
#define eps (1e-8)
#define mod 1000000007
#define pi acos(-1)
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(),(a).end()
#define pd(a) printf("%.10f\n",(double)(a))
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i=(a)-1;(b)<=i;i--)
#define equals(a,b) (fabs((a)-(b))<eps)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<int,double> pid;
typedef pair<double,int> pdi;
typedef vector<int> vi;
typedef vector<pii> vpi;
const int dx[8]={1,0,-1,0,1,1,-1,-1};
const int dy[8]={0,1,0,-1,1,-1,1,-1};

int m,n;
int X1[MAX],Y1[MAX];
int X2[MAX],Z2[MAX];

double width(int* X,int* Y,int N,double x){
  double lb=inf,ub=-inf;
  FOR(i,0,N){
    double x1=X[i],y1=Y[i],x2=X[(i+1)%N],y2=Y[(i+1)%N];
    if((x1-x)*(x2-x)<=0 && x1!=x2){
      double y=y1+(y2-y1)*(x-x1)/(x2-x1);
      lb=min(lb,y);
      ub=max(ub,y);
    }
  }
  return max(0.0,ub-lb);
}

double solve(){
  int min1=*min_element(X1,X1+m),max1=*max_element(X1,X1+m);
  int min2=*min_element(X2,X2+n),max2=*max_element(X2,X2+n);
  vector<double> xs;
  FOR(i,0,m)xs.pb(X1[i]);
  FOR(i,0,m)xs.pb(X2[i]);
  sort(all(xs));

  double res = 0.0;
  FOR(i,0,xs.size()-1){
    double a=xs[i],b=xs[i+1],c=(a+b)/2.0;
    if(min1<=c && c<=max1 && min2<=c && c<=max2){
      double fa=width(X1,Y1,m,a)*width(X2,Z2,n,a);
      double fb=width(X1,Y1,m,b)*width(X2,Z2,n,b);
      double fc=width(X1,Y1,m,c)*width(X2,Z2,n,c);
      res+=(b-a)/6.0*(fa+fb+fc*4.0);
    }
  }
  return res;
}

int main()
{
  while(cin>>m>>n && m){
    FOR(i,0,m)cin>>X1[i]>>Y1[i];
    FOR(i,0,n)cin>>X2[i]>>Z2[i];
    pd(solve());
  }
  return 0;
}

Measured memory_bytes: 3140
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<list>
#include<unordered_map>
using namespace std;
#define ll long long
#define dd cout<<endl
const int mod=1e9+7;
const int inf=1e9+7;
   
//const int maxn=

  
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
      
    ll int a,b;
    
    while(cin>>a>>b)
    {
    	if((a+b)&1)
    	{
    		cout<<"IMPOSSIBLE"<<endl;
    		continue;
		}
		
		cout<<(a+b)/2<<endl;
	}
      
      
    return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String input = null;
		try {
			input = br.readLine();
			br.close();
		} catch (IOException e) {
		}
		String[] WHxyr = input.split(" ");

		int W = Integer.parseInt(WHxyr[0]);
		int H = Integer.parseInt(WHxyr[1]);
		int x = Integer.parseInt(WHxyr[2]);
		int y = Integer.parseInt(WHxyr[3]);
		int r = Integer.parseInt(WHxyr[4]);
		
		if(W >= (x + r) && H >= (y + r) && 0 <= (x - r) && 0 <= (y - r)){
		    System.out.println("Yes");
		}else{
		    System.out.println("No");
		}
	}
}


Measured memory_bytes: 24460
import sys
input = sys.stdin.readline
ri = lambda: int(input())
#rl = lambda: [int(x) if x.isdecimal() else x for x in input().split()]
#rl = lambda: list(input().split()))
rl = lambda: map(int,input().split())
rr = lambda N: [list(l) for l in zip(*[rl() for _ in range(N)])]
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')
OE = lambda x: print('Odd') if x%2 else print('Even')
INF = 10**18
MOD = 10**9+7

S=input().rstrip()
a=int(S[:2])
b=int(S[2:])
if 1<=a and a<=12 and 1<=b and b<=12:
    print('AMBIGUOUS')
elif 1<=b and b<=12:
    print('YYMM')
elif 1<=a and a<=12:
    print('MMYY')
else:
    print('NA')


Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iomanip>
#include <random>
#include <cstdio>
#include <cmath>
#include <map>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (int) n; i++)

int main() {
    vector<string> day = {"SUN", "MON", "TUE", "WED", "THU", "FRI", "SAT"};
    string s; cin >> s;
    for (int i = 0; i < 7; i++) {
        if (day[7-i-1] == s) {
            cout << i+1 << endl;
            return 0;
        }
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <iomanip>
#include <climits>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<string> VS;
typedef vector< vector<int> > VVI;
typedef vector< vector<ll> > VVL;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define all(a) (a).begin(),(a).end()
#define pf push_front
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define ub upper_bound
#define lb lower_bound

int main(){
  double X;
  cin>>X;
  ll tmp=100;
  rep(i,100000){
    tmp*=1.01;
    if(tmp>=X){
      cout<<i+1<<endl;
      break;
    }
  }
}


Measured memory_bytes: 3720
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;


void countingsort(int *A, int *B, int k, int n){
    int i,j;
    int C[1000000];
    for(i=0;i<k+1;i++) C[i]=0;

    for(i=0;i<n;i++) C[A[i]]++;

    for(i=1;i<k+1;i++){
        C[i]=C[i] + C[i-1];
    }

    for(i=n-1;i>=0;i--){
        B[C[A[i]]-1] = A[i];
     // printf("%d\n", A[i]);
        C[A[i]]--;
    }
}

int main(){
    int n;
    scanf("%d", &n);
    int *A = (int *)malloc(sizeof(int)*n);
    int *B = (int *)malloc(sizeof(int)*n);

    for(int i=0;i<n;i++) scanf("%d", &A[i]);
    countingsort(A, B, 10000, n);
    for(int i=0;i<n;i++){
        if(i==n-1)printf("%d", B[i]);
        else printf("%d ", B[i]);
    }
    printf("\n");
    free(A);
    free(B);

}


Measured memory_bytes: 18404
#include<stdio.h>
#include<math.h>
long n,a;
long max = 0;
long min = 1000000001;
int main() {
	scanf("%ld",&a);
	for (long i = 0; i < a; i++) {
		scanf("%ld", &n);
		if (n > max)max = n;
		if (n < min)min = n;
	}
	printf("%ld", max - min);
}

Measured memory_bytes: 128
#include"bits/stdc++.h"
using namespace std;
#define int long long
#define con continue
#define rep(i,n) for(int i=0;i<n;i++)
const long long mod = 1000000007;
const long long inf = 1ll<<61;
typedef pair<int, int> P;
typedef pair<P, int> PP;
typedef pair<int, PP> PPP;
struct edge { int to; int to2; int cost; };

int a[100006], b[100006];
int ubit[35];
int hbit(int a) {
	int res = -1;
	while (a) {
		res++; a >>= 1;
	}
	return res;
}

signed main() {
	int n, k; cin >> n >> k;
	rep(i, n)cin >> a[i] >> b[i];
	int K = hbit(k);
	int sum = 0;
	for (int i = K; i >= 0; i--) {
		if (k&(1 << i)) {
			for (int j = K; j >= 0; j--) {
				if (i == j)ubit[j] = 0;
				else if (i < j)ubit[j] = k & 1 << j ? 1 : 0;
				else ubit[j] = 1;
			}
		}
		else {
			rep(j, K + 1)ubit[j] = k&(1 << j) ? 1 : 0;
		}
			int res = 0;
			rep(j, n) {
				int flg = 0;
				if (a[j] > k)flg++;
				rep(l, K + 1) {
					if ((a[j] & (1 << l)) && !ubit[l])flg++;
				}
				if (!flg)res += b[j];
			}
			sum = max(sum, res);
	}

	rep(j, K + 1)ubit[j] = k&(1 << j) ? 1 : 0;
	int res = 0;
	rep(j, n) {
		int flg = 0;
		if (a[j] > k)flg++;
		rep(l, K + 1) {
			if ((a[j] & (1 << l)) && !ubit[l])flg++;
		}
		if (!flg)res += b[j];
	}
	sum = max(sum, res);
	cout << sum << endl;
}

Measured memory_bytes: 1792
import qualified Data.Text as T
import qualified Data.Text.IO as T
import qualified Data.Text.Read as T

main :: IO ()
main = do
  (x : _) <- map unsafeSignedDecimal . T.words <$> T.getLine :: IO [Int]
  print .  head . dropWhile (< x) $ primes

primes :: [Int]
primes = 2 : 3 : f 2 candidates
  where
    f :: Int -> [Int] -> [Int]
    f l cs = c' : f (succ l) cs'
      where
        (c' : cs') = dropWhile (\c -> any ((== 0) . mod c) (take l primes)) cs
    candidates :: [Int]
    candidates = [1..] >>= \i -> (6 * i +) <$> [(-1), 1]

unsafeSignedDecimal :: T.Text -> Int
unsafeSignedDecimal s = case T.signed T.decimal s of
  Right (n, _) -> n


Measured memory_bytes: 2684
#include<iostream>
#include<string>
#include<cstdio>
#include <cstring>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
typedef long double ld;
const ll INF = 1e+14;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
#define fr first
#define sc second
#define all(c) c.begin(),c.end()
#define pb push_back

void Yes(){
	cout<<"Yes"<<endl;
	exit(0);
}
 
void No(){
	cout<<"No"<<endl;
	exit(0);
}

ll C[51][51];

void comb_table(int N){
    for(int i = 0;i <= N; ++i){
        for(int j = 0;j <= i; ++j){
            if(j == 0 || j == i){
                 C[i][j] = 1LL;
            }else{
                C[i][j] = C[i-1][j-1] + C[i-1][j];
            }
        }
    }
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
    int N, A, B; cin >> N >> A >> B;
    comb_table(N);
    ld v[55]; rep(i, N) cin >> v[i];
    sort(v, v + N, greater<ll>());
    ld mini = v[A - 1]; 
    int cnt = 0, cnt1 = 0;
    rep(i, N) {
        if(v[i] == mini) cnt ++;
    }
    ld ans = 0;
    rep(i, A) {
        ans += v[i];
        if(v[i] == mini) cnt1 ++;
    }
    ans /= A;
    cout << fixed << setprecision(8) << ans << endl;
    if(v[0] != mini) {
        cout << C[cnt][cnt1] << endl;
    } else {
        ll ans1 = 0;
        Rep(i, A, B + 1) {
            if(cnt < i) break;
            ans1 += C[cnt][i];
        }
        cout << ans1 << endl;
    }
	return 0;
}

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

#define REP(i, n) for(decltype(n) i = 0; i < n; i++)

#define ALL(c)   c.begin(), c.end()
#define SORT(c)  std::sort(ALL(c))
#define RSORT(c) std::sort(ALL(c), std::greater<decltype(c)::value_type>())

using namespace std;
using ll = long long;

const int MOD  = (int)1e9 + 7;
const int INF  = (int)1e9 + 1;
const ll  LINF = (ll)1e18 + 1;

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

    int n;
    std::cin >> n;

    vector<int> A(n);
    REP(i, n) {
        std::cin >> A[i];
    }

    int N = *max_element(ALL(A));

    int    r_index = 0;
    double min_val = INF;
    REP(i, n) {
        if(A[i] == N) continue;
        double val = abs(N / 2.0 - A[i]);
        if(val < min_val) {
            min_val = val;
            r_index = i;
        }
    }

    std::cout << N << " " << A[r_index] << std::endl;

    return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 3e3 + 50;
ll mod = 998244353;
ll qm(ll a, ll b) {
	ll res = 1;
	while (b) {
		if (b & 1)res = res * a % mod;
		a = a * a % mod, b >>= 1;
	} return res;
}
ll a[maxn], b[maxn], c[maxn], temp[maxn];
ll x[maxn], y[maxn];
ll n;
void mul(ll *f, int len, ll t) { //len为多项式的次数+1，函数让多项式f变成f*(x+t)
	for (int i = len; i > 0; --i) temp[i] = f[i], f[i] = f[i - 1];
	temp[0] = f[0], f[0] = 0;
	for (int i = 0; i <= len; ++i) f[i] = (f[i] + t * temp[i] + mod) % mod;
}
void dev(ll *f, ll *r, ll t) { //f是被除多项式的系数，r保存f除以x+t的结果
	for (int i = 0; i <= n; ++i) temp[i] = f[i];
	for (int i = n; i > 0; --i) {
		r[i - 1] = temp[i];
		temp[i - 1] = (temp[i - 1] - t * temp[i] + mod) % mod;
	}
	return;
}
void lglr() {
	memset(a, 0, sizeof a);
	b[1] = 1, b[0] = -x[1];
	for (int i = 2; i <= n; ++i) {
		mul(b, i, -x[i]);
	}//预处理(x-x1)*(x-x2)...*(x-xn)
	for (int i = 1; i <= n; ++i) {
		ll fz = 1;
		for (int j = 1; j <= n; ++j) {
			if (j == i) continue;
			fz = (fz * (x[i] - x[j]) + mod) % mod;
		}
		fz = qm(fz, mod - 2);
		fz = ((fz * y[i] % mod) + mod) % mod; //得到多项式系数
		dev(b, c, -x[i]);//得到多项式，保存在b数组
		for (int j = 0; j < n; ++j) a[j] = (a[j] + fz * c[j] + mod) % mod;
	}
}
int main()
{
	cin >> n;
	mod = n;
	for (int i = 1; i <= n; ++i)
	{
		x[i] = i - 1;
		cin >> y[i];
	}

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


Measured memory_bytes: 512
# Nで指定された桁に入り切らないケースは「1 ≤ si ≤ N」よりあり得ない
N, M = gets.split.map(&:to_i)
s, c = [], Array.new(N)

M.times do
  _s, _c = gets.split.map(&:to_i)
  s << _s

  # 同一桁に違う値が指定されている場合
  if c[_s - 1] && c[_s - 1] != _c
    puts -1

    exit
  end

  c[_s - 1] = _c
end

# 1桁目が0の場合はNG(ただし1桁の場合は0を許容する)
if N != 1 && s.find { |_s| _s == 1 && c[_s - 1].zero? }
  puts -1

  exit
end

puts c[0..(N - 1)].map.with_index { |_c, i| _c ? _c : (i.zero? && N != 1 ? 1 : 0) }.join


Measured memory_bytes: 1788
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    private static int cnt;
    public static void main(String[] args) throws Exception {
        BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
        int n = readInt(r);
        int[] A = new int[n];
        for (int i = 0;i < n;i++) {
            A[i] = readInt(r);
        }

        shellSort(A, n);
        System.out.println(cnt);
        for (int i = 0;i < n;i++) {
            System.out.println(A[i]);
        }
    }

    public static void insertionSort(int[] A, int n, int g) {
        for (int i = g;i < n;i++) {
            int v = A[i];
            int j = i - g;
            while (j >= 0 && A[j] > v) {
                A[j + g] = A[j];
                j = j - g;
                cnt++;
            }
            A[j + g] = v;
        }
    }

    public static void shellSort(int[] A, int n) {
        cnt = 0;
        int[] tmpG = new int[100];
        int m = 0;
        for (int x = 1;;) {
            if (x > n) break;
            tmpG[m++] = x;
            x = 3 * x + 1;
        }
        
        int[] G = new int[m];
        for (int i = 0;i < m;i++) {
            G[i] = tmpG[m - i - 1];
        }
        
        System.out.println(m);
        System.out.println(dump(G, m));

        for (int i = 0;i < m;i++) {
            insertionSort(A, n, G[i]);
        }
    }

    // Stable: true
    // Unstable: false
    public static void swapInt(int[] A, int j, int k) {
        int v = A[j];
        A[j] = A[k];
        A[k] = v;
    }
    
    public static String dump(int[] A, int N) {
        StringBuilder builder = new StringBuilder();
        for (int i = 0;i < N;i++) {
            if (i != 0) {
                builder.append(" ");
            }
            builder.append(A[i]);
        }
        return builder.toString();
    }
    
    public static int readInt(BufferedReader r) throws Exception {
        return Integer.parseInt(r.readLine());
    }
}

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

main() {
    int N,K; cin >> N >> K;
    if(N%K==0) cout << 0 << endl;
    else cout << 1 << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define SORT(a) sort(a.begin(), a.end())
#define RSORT(a) sort(a.rbegin(), a.rend())
#define REP(i, n) for (long long i = 0; i < n; i++)
#define RREP(i, n) for (long long i = n - 1; 0 <= i; i--)
#define FOR(i, start, end) for (long long i = start; i < end; i++)
#define RFOR(i, start, end) for (long long i = start - 1; 0 <= i; i--)
#define ALL(a) a.begin(), a.end()
#define MOD(a) a %= 1'000'000'007
using ll = long long;
using namespace std;
const int INF32       = 1'050'000'000;
const long long INF64 = 4'000'000'000'000'000'000;
const int MOD7        = 1'000'000'007;
const int MOD9        = 1'000'000'009;
template <class T> inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
void print() { std::cout << '\n'; }
template <class H, class... T> void print(H &&head, T &&... args) {
    std::cout << head;
    sizeof...(args) == 0 ? std::cout << "" : std::cout << ' ';
    print(std::forward<T>(args)...);
}
template <class T> void print(std::vector<T> &v) {
    for (int i = 0; i < v.size(); i++) {
        std::cout << v[i];
        i == v.size() - 1 ? std::cout << '\n' : std::cout << ' ';
    }
}
template <class T> void print(std::vector<std::vector<T>> &v) {
    for (int i = 0; i < v.size(); i++) {
        for (int j = 0; j < v[i].size(); j++) {
            std::cout << v[i][j];
            j == v[i].size() - 1 ? std::cout << '\n' : std::cout << ' ';
        }
    }
}

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

    string s;
    cin >> s;
    vector<ll> dp(13);
    dp[0]       = 1;
    ll time     = 1;
    const int N = 13;
    RREP(i, s.size()) {
        vector<ll> nxt(13);
        if (s[i] != '?') {
            int k = s[i] - '0';
            REP(j, N) {
                nxt[(k * time + j) % N] += dp[j];
                MOD(nxt[(k * time + j) % N]);
            }
        } else {
            REP(k, 10) {
                REP(j, N) {
                    nxt[(k * time + j) % N] += dp[j];
                    MOD(nxt[(k * time + j) % N]);
                }
            }
        }
        time *= 10;
        time %= N;
        dp = nxt;
    }
    print(dp[5]);

    return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    int ans=0;
    for(int i=1; i<=n; i++){
        if(i*i<=n){
            ans=i*i;
        }else{
            break;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>

using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> P;
typedef vector<P> vpl;
#define rep(i,n) for(ll i=0; i<(n); i++)
#define REP(i,a,b) for(ll i=(a); i<(b); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const int inf = 1<<30;
const ll linf = 1LL<<62;
const int mod = 1e9+7;
const int MAX = 510000;
const int V = 100005;
ll dy[8] = {1,0,-1,0,1,-1,1,-1};
ll dx[8] = {0,1,0,-1,1,-1,-1,1};
const double pi = acos(-1);
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;}
template<typename T1,typename T2> inline void print2(T1 a, T2 b){cout << a << " " << b << endl;}
#define INT_MAX 1e9+7

int main(){
    ll n; cin >> n;
    string s; cin >> s;
    vector<char> t;
    ll ans = 0;
    rep(i,10){
        rep(j,10){
            rep(k,10){
                bool iflag = false;
                bool jflag = false;
                bool kflag = false;
                rep(l,n){
                    if(s[l]-'0'==i && !iflag){
                        iflag = true;
                        continue;
                    }
                    if(s[l]-'0'==j && iflag && !jflag){
                        jflag = true;
                        continue;
                    }
                    if(s[l]-'0'==k && jflag){
                        ans++;
                        break;
                    }
                }
            }
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <map>
#include <set>
using namespace std;
int main(void){
    map<int,int> m1;
    map<string,int>m2;
    int n,m,p;
    string s;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        cin>>p>>s;
        if(s=="WA"){
            if(m1[p]!=-1){
                m1[p]++;
            }
        }else if(s=="AC"){
            if(m1[p]!=-1){
                m2["AC"]++;
                m2["WA"]+=m1[p];
                m1[p]=-1;
            }
        }else{
            cout<<"error";
        }
    }
    cout<<m2["AC"]<<" "<<m2["WA"];
}


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

int main()
{
  int cnt=0;
  int n,m;
  cin >> n >> m;
  for(int i=n;i<=m;i++)
  {
    string s=to_string(i);
    if(s.at(0)==s.at(4)&&s.at(1)==s.at(3)) cnt++;
  }
  cout << cnt << endl;
}

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

/* #pragma */
/*
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
*/

/*alias*/
#define F first
#define S second

#define y0 y3487465
#define y1 y8687969
#define j0 j1347829
#define j1 j234892
#define next asdnext
#define prev asdprev
#define itn int

/*template*/
template<class T>inline bool amax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>inline bool amin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }

/* func */
int GCD(int a,int b){return b?GCD(b,a%b):a;}
long long GCD(long long a, long long b){return b ? GCD(b, a%b) : a;}
int LCM(int a, int b){return a * b / GCD(a, b);}
long long LCM(long long a, long long b){return a * b / GCD(a, b);}

/*struct*/
struct aaa {
	aaa() {
		cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20);
	};
}aaaaaaa;

/* const */
const int INF = 1001001001;
const long long LINF = 1001001001001001001ll;
const int MOD = 1e9 + 7; //10^9
const double EPS = 1e-9;
const int dx[] = { 1, 1, 0, -1, -1, -1, 0, 1 }, dy[] = { 0, 1, 1, 1, 0, -1, -1, -1 };
//const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
//Counterclockwise from the 6o'clock direction
//Take the x-axis downward and the y-axis right

//#define int long long

//g++ -std=c++14 -Wall --pedantic-errors -o template template.cpp
//g++ -std=c++14 -Wall --pedantic-errors template.cpp
//chcp 65001

/*global*/




signed main()
{
	int a,b,c,d;cin >> a >> b >> c >> d;
	int dis = d-b;
	int dis2 = c-a;	
	int x4 = a-dis;
	int x3 = c-dis;
	int y3 = dis2+d;
	int y4 = dis2+b;
	cout << x3 << " " << y3 << " " << x4 << " " << y4 << endl;
}

Measured memory_bytes: 256
// --------------------------------------------
// ****************  gzhffIThh  ***************
// --------------------------------------------
// #pragma GCC optimize(2)
// #pragma GCC optimize(3)

#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>
#include <map>

using namespace std;


struct rec {
	int x, y, st;
	rec() : x(), y(), st() {}
	rec(int _x, int _y, int _st) : x(_x), y(_y), st(_st) {}
} ;

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

        int n, m, k;

        cin >> n >> m >> k;

        string s[810];

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

        int si(0), sj(0);
        for (int i = 0; i < n; i++) {
        	for (int j = 0; j < m; j++) {
        		if (s[i][j] == 'S') {
        			si = i;
        			sj = j;
        			break;
        		}
        	}
        }

        int det[4][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} };

        int ans = min(min(m - (sj + 1),(sj + 1) - 1),  min(n - (si + 1), (si + 1) - 1));

        ans = ans / k + (ans % k > 0) + 1;

        int tmp = ans;

        queue<rec> q;
        map<pair<int, int>, int> used;
        q.push(rec(si, sj, 0));

        while (q.size()) {
        	rec now = q.front();
        	q.pop();

        	if (now.st == k) break;

        	for (int d = 0; d < 4; d++) {
        		int di = now.x + det[d][0], dj = now.y + det[d][1];

        		if (di < 0 || di >= n || dj < 0 || dj >= m || s[di][dj] == '#') continue;

        		if (used.find(make_pair(di, dj)) != used.end()) continue;

        		used[make_pair(di, dj)] = 1;

        	    	int tmp = min(min(m - (dj + 1), (dj + 1) - 1),  min(n - (di + 1), (di + 1) - 1));

        		tmp = tmp / k + (tmp % k > 0) + 1;

        		ans = min(ans, tmp);

        		q.push(rec(di, dj, now.st + 1));

        	}
        }

        cout << ans << '\n';

        return 0; 
}

Measured memory_bytes: 43460
#include<bits/stdc++.h>
using namespace std;
int c[5][5],b11,b12,b13,b21,b22,b23,b31,b32,b33;
int main(){
    for(int i=1;i<=3;i++) for(int j=1;j<=3;j++) cin>>c[i][j];
    for(int a1=0;a1<=100;a1++){
        b11=c[1][1]-a1;
        b21=c[1][2]-a1;
        b31=c[1][3]-a1;
        for(int a2=0;a2<=100;a2++){
            b12=c[2][1]-a2;
            b22=c[2][2]-a2;
            b32=c[2][3]-a2;
            if(b11!=b12 || b21!=b22 || b31!=b32) continue;
            for(int a3=0;a3<=100;a3++){
	            b13=c[3][1]-a3;
	            b23=c[3][2]-a3;
	            b33=c[3][3]-a3;
	            if(b11==b13 && b21==b23 && b31==b33){
		            cout<<"Yes"<<endl;
		            return 0;
	            }
            }
        }
    }
    cout<<"No"<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); ++i)
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)
#define fi first
#define se second
#define INF 1000000009
#define LLINF 1000000000000000009LL
using ll = long long;

int main(){
  ll n,d;
  cin>>n>>d;
  int ans=0;
  rep(i,n){
    ll x,y;
    cin>>x>>y;
    if(x*x+y*y<=d*d)ans++;
  }
  cout<<ans<<endl;
  return(0);
}

Measured memory_bytes: 3524
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,k; cin >> n >> k;
    int a[n+1], dp[n+1];
    for(int i=1; i<= n; i++){
        cin >> a[i];
        dp[i] = 1e9+5;
    }
    dp[0] = 0;
    dp[1] = 0;
    for(int i =1; i<= n; i++){
        for(int j = 1; j<= k; j++){
            if(i-j > 0){
                dp[i] = min(dp[i], dp[i-j]+ abs(a[i]- a[i-j]));
            }
        }
    }

    
    cout << dp[n] << endl;
    return 0;

}



Measured memory_bytes: 4360
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <numeric>
#include <complex>
using namespace std;

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

int main() {
    string S;
    cin >> S;
    rep(i, S.size()) {
        if (i % 2 == 0) {
            cout << S[i];
        }
    }
    cout << endl;
}

Measured memory_bytes: 512
#include <stdio.h>
#include <stack>
using namespace std;
struct hollow{
    int n;
    int l;
};
int main(){
    int now=0,ans=0,t=0,c[20001];
    stack<int> d;
    stack<hollow>b;
    hollow temp;
    char a[20001];
    for(int i=0;i<20001;i++)a[i]='\0';
    scanf("%s",a);
    while(a[now]!='\0'){
        if(a[now]=='\\')d.push(now);
        if(a[now]=='/'&&!d.empty()){
            temp.n=now-d.top();
            temp.l=d.top();
            d.pop();
            while(!b.empty()&&b.top().l>temp.l){
                temp.n+=b.top().n;
                b.pop();
            }
            b.push(temp);
        }
        now++;
    }
    while(!b.empty()){
        c[t]=b.top().n;
        ans+=c[t];
        t++;
        b.pop();
        
    }
    printf("%d\n%d",ans,t);
    for(int i=t-1;i>=0;i--)printf(" %d",c[i]);
    printf("\n");
}


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

int main(){
  int N;
  cin >> N;
  vector<int> A(N+1);//2からN
  vector<int> B(N+1);//1からN
  for(int i=2; i<N+1; i++){
    cin >> A[i];
    B[A[i]]++;//A[i]の部下の数を+1
  }
  for(int i=1; i<N+1; i++){
    cout << B[i] << endl;
  }
  return 0;
}


Measured memory_bytes: 4760
#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <sstream>
#include <bitset>
#include <memory>
#include <string>
#include <vector>
#include <queue>
#include <list>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <deque>
#include <algorithm>
#include <random>
#include <iomanip>
using namespace std;

int main(int argc, char *argv[]) {
	string s;
	cin >> s;
	if (s.size() % 2 == 1) {
		cout << "No" << endl;
		return 0;
	}
	for (int i = 0; i < s.size(); i++) {
		if (i % 2 == 0) {
			if (s[i] == 'h') {

			}
			else {
				cout << "No" << endl;
				return 0;
			}
		}
		else {
			if (s[i] == 'i') {

			}
			else {
				cout << "No" << endl;
				return 0;
			}
		}
	}
	cout << "Yes" << endl;
	return 0;
}









Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
const ll mod = 1000000007;
ll findProductSum(int A[], int n) { 
    vector<long long> dp(n);
    for (int i = n-2; i >= 0; i--) dp[i] = (dp[i+1] + A[i+1]) % mod; 
    ll individual_square_sum = 0; 
    for (int i = 0; i < n - 1; i++) {individual_square_sum += ((A[i] * dp[i]) %mod);}
    return individual_square_sum; 
} 
int32_t main() {
    ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    ll n; cin>>n;
    int arr[200001];
    for(int i = 0; i < n; i++) cin >> arr[i];
    cout << findProductSum(arr, n) % mod;
}


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

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag, tree_order_statistics_node_update> indexed_multiset;

const long long MAXN = 2e5+5;
long long arr[MAXN];
long long pref[MAXN];
long long val[MAXN];
long long ans = 0;
int main(){
    indexed_multiset s1;
    long long n,k;
    cin>>n>>k;
    for(long long i=1;i<=n;i++){
        cin>>arr[i];
        pref[i] = pref[i-1]+arr[i];
        val[i] = pref[i-1]-(k*i);
    }
    val[n+1] = pref[n]-(k*(n+1));
    for(long long i=1;i<=n+1;i++){
        ans+=s1.order_of_key(val[i]+1);
       // cout<<val[i]<<" "<<s1.order_of_key(val[i])<<" "<<ans<<endl;
        s1.insert(val[i]);
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 17408
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <deque>
#include <stack>
#include <cctype>
using namespace std;
typedef long long ll;
typedef vector<int> veci;
typedef vector<ll> vecl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template <class T>
inline void read(T &ret) {
    char c;
    int sgn;
    if (c = getchar(), c == EOF) return ;
    while (c != '-' && (c < '0' || c > '9')) c = getchar();
    sgn = (c == '-') ? -1:1;
    ret = (c == '-') ? 0:(c - '0');
    while (c = getchar(), c >= '0' && c <= '9') ret = ret * 10 + (c - '0');
    ret *= sgn;
    return ;
}
inline void outi(int x) {if (x > 9) outi(x / 10);putchar(x % 10 + '0');}
inline void outl(ll x) {if (x > 9) outl(x / 10);putchar(x % 10 + '0');}
typedef long long ll;
int main()
{
    int x;
    read(x);
    if(x==1)
        cout<<"0"<<endl;
    else
        cout<<"1"<<endl;
}



Measured memory_bytes: 3600
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int k = sc.nextInt();
		long[] a = new long[n+1];
		a[0] = 0;
		for(int i = 1; i <= n; i++) {
			a[i] = sc.nextLong()+a[i-1];
		}
		long[] b = new long[m+1];
		b[0] = 0;
		for(int i = 1; i <= m; i++) {
			b[i] = sc.nextLong()+b[i-1];
		}
		int j = m;
		int max = 0;
		for(int i = 0; i <= n; i++) {
			if(a[i] > k) {
				break;
			}
			while(j >= 0 && k-a[i] < b[j]) {
			j--;
			}
			max = Math.max(i+j, max);
		}
		System.out.println(max);
	}
}


Measured memory_bytes: 64604
#include <bits/stdc++.h>
#define N 5005
#define rep(i,a,b) for(int i=a;i<b;i++)
using namespace std;
int n,k;
int a[N];
vector <int> b[N];
bool dp[N][N];
int read()
{
	int x=0;
	char ch=' ';
	bool flag=false;
	while(!isdigit(ch))
	{
		if(ch=='-')flag=true;
		ch=getchar();
	}
	while(isdigit(ch))
	{
		x=(x<<3)+(x<<1)+ch-'0';
		ch=getchar();
	}
	return flag?-x:x;
}
int Inboard(int x)
{
	if(x>k)x=k;
	return x;
}
void Init()
{
	n=read(),k=read();
	rep(i,0,n)
	{
		a[i]=read();
		a[i]=Inboard(a[i]);
	}
	sort(a,a+n);
	rep(i,0,n)
	{
		rep(j,0,n)
		{
			if(i!=j)b[i].push_back(a[j]);
		}
	}
}
bool check(vector <int> ai,int x)
{
	if(ai.empty())return x>=k;
	if(ai.size()==1)return ai[0]>=k-x && ai[0]<k;
	memset(dp,false,sizeof(dp));
	dp[0][0]=true;
	dp[0][ai[0]]=true;
	int np=n-1;
	rep(i,1,np)
	{
		rep(j,0,k)
		{
			dp[i][j]=dp[i][j] || dp[i-1][j];
			if(j>ai[i])dp[i][j]=dp[i][j] || dp[i-1][j-ai[i]];
		//	dp[i+1][j]|=dp[i][j];
		//	dp[i+1][Inboard(j+ai[i])]|=dp[i][j];
		}
	}
	int low=k-x;
/*	rep(i,0,np)
	{
		rep(j,0,k)
		{
			cout<<dp[i][j]<<" ";
		}
		cout<<endl;
	}*/
	rep(i,low,k)
	{
		if(dp[np-1][i])return true;
	}
	return false;
}
void Solve()
{
	int lb=0,ub=n;
	while(lb<ub)
	{
		int mid=(lb+ub)/2;
		if(check(b[mid],a[mid]))
		{
			ub=mid;
		}
		else
		{
			lb=mid+1;
		}
	}
	cout<<lb<<endl;
}
int main()
{
	Init();
	Solve();
	return 0;
}

Measured memory_bytes: 142464
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define INF -99999999
typedef pair<int,int> P;
int main(void) {
  ll N,A,B;cin>>N>>A>>B;

  ll res = 0;

  res += (N/(A+B))*A;
  res += min(N%(A+B),A);

  cout<<res<<endl;

  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <numeric>
#include <math.h>
#include <algorithm>
#include <float.h>
#include <limits>
#include <vector> 
#include <string.h>
#include <iomanip>

#define rep(i,a,n) for(ll int (i) = (a);(i) < (n);(i)++)
#define urep(i,a,n) for(ll int (i) = (a);(i) > (n);(i)--)
#define MOD 1000000007
#define ll long long
#define asort(a) sort(a.begin(),a.end());

using namespace::std;

int jo(ll int jxo, ll int jyo){//累乗
    ll int jhogeo = 1;
    rep(jinto,0,jyo) jhogeo=jhogeo*jxo;
    return jhogeo;
}
char tobig(char toxbig){//char大文字化
  return (toxbig-0x20);
}
char tolow(char toxlow){//char小文字化
  return (toxlow+0x20);
}
int ctoi(char cctoi){//char->int
  if('0' <= cctoi && cctoi <= '9') return (cctoi-'0');
  return -1;
}

int gcd(int gcad, int gcbd) {//最大公約数
  if(gcad < gcbd) return gcd(gcbd, gcad);
  int gcrd;
  while ((gcrd=gcad%gcbd)) {
    gcad = gcbd;
    gcbd = gcrd;
  }
  return gcbd;
}
int lcm(int lcam, int lcbm){//最小公倍数
 return (lcam*lcbm)/gcd(lcam,lcbm);
}

int sei(ll int sssei){
  if(sssei>0){
    return sssei;
  }else{
    return 0;
  }
}
int F(ll a,ll b){
  int aa=to_string(a).length();
  int bb=to_string(b).length();
  return max(aa,bb);
}

int main(){
  ll int N; cin>>N;
  int ans=11;
  rep(i,1,sqrt(N)+1){
    if(!(N%i)){
      if(ans>F(i,N/i)) ans=F(i,N/i);
    }
  }
  cout<<ans;
}
// int *p = new int[N];

//  vector<int> 変数名(要素数);
//  sort(変数名.begin(),変数名.end());//昇順ソート

// vector<vector<int>> 変数名(左の個数, vector<int>(右の個数));

//cout<<fixed<<setprecision(n);  //小数点n桁まで表示

//  vector<pair<int,int>> data(N);  //2つのデータを格納、.first/.secondで参照
// pairのソートはfirst優先の昇順

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{   int n, m, ans=0;
    cin >> n >> m;
    for (int i = n-1; i >= 1; i--)
        ans += i;
    for (int j = m-1; j >= 1; j--)
        ans += j;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define lli long long int
#define ulli unsigned lli
#define ld long double
#define pb push_back
#define mp make_pair
#define bp pop_back
#define vi vector<int>
#define vvi vector< vector<int> >
#define vli vector<lli>
#define vvli vector< vector<lli> >
#define pii pair <int, int>
#define pli pair <lli, lli>
#define vpi vector<pii>
#define ppi pair<pii,int>
#define pip pair<int,pii>
#define forn(i,n) for(i=0;i<n;i++)
#define rof(i,k,n) for(i=k;i>=n;i--)
#define wh(k) while(k--)
#define mod 1000000007
#define all(i,m) auto i=m.begin();i!=m.end();i++
#define mii map<int,int>
#define F first
#define S second

const int MAX=1000000;

int main()
{
    fast;
    lli a,b,c,d;
    cin>>a>>b>>c>>d;
    lli ans=LLONG_MIN;
    ans=max(b*d,ans);
    ans=max(ans,a*c);
    ans=max(ans,b*c);
    ans=max(ans,a*d);
    if(a*b<=0||c*d<=0)
    	ans=max(ans,(lli)0);
    cout<<ans<<'\n';
    return 0;
}

Measured memory_bytes: 3652
import java.util.Scanner;

final class Solver {
	static final Solver INSTANCE = new Solver();

	void solve(Scanner sc) {
		int N = sc.nextInt();
		int M = sc.nextInt();
		if (N == 1 && M == 1) {
			System.out.println(1);
		} else if (N == 1) {
			System.out.println(M - 2);
		} else if (M == 1) {
			System.out.println(N - 2);
		} else if (N > 3 && M > 3) {
			System.out.println((N - 2L) * (M - 2L));
		} else {
			System.out.println(0);
		}
	}
}

class Main {
	public static void main(String... args) {
		Scanner in = new Scanner(System.in);

		Solver.INSTANCE.solve(in);

		in.close();
	}
}

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

char S[16];
int main(void){
  cin>>S;
  int cnt=0, ocnt=0;
  for(uint i=0; i<strlen(S); i++){
    cnt++;
    if( S[i] == 'o' ) ocnt++;
  }
  if( 15-cnt + ocnt < 8 ) cout<<"NO"<<endl;
  else cout<<"YES"<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <iomanip>
#include <set>
#include <ctime>
#include <tuple>
#include <bitset>
using namespace std;

/*
sort(sp.begin(), sp.end(), [](PAIR l, PAIR r){
        return l.first<r.first || (l.first==r.first && l.second > r.second);
        });
*/

typedef long long ll;

#define fi first
#define se second

using Graph = vector<vector<int>>;

int main()
{
    ll n, k;
    cin >> n >> k;
    vector<ll> a(n);
    for (ll i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    vector<ll> b(n, -1);
    if (n >= k)
    {
        ll ans = 1;
        for (ll i = 0; i < k; i++)
        {
            ans = a[ans - 1];
        }
        cout << ans << endl;
        return 0;
    }
    b[0] = 0;
    ll tmp = 0;
    ll loop = 0;
    for (ll i = 0; i < n; i++)
    {
        if (b[a[tmp] - 1] == -1)
        {
            b[a[tmp] - 1] = i + 1;
            tmp = a[tmp] - 1;
        }
        else
        {
            loop = i;
            break;
        }
    }
    ll mod = loop + 1 - b[a[tmp] - 1]; //戻ってくるまでに何回かかったか
    k = (k - b[a[tmp] - 1]) % mod;

    // tmp++;
    tmp = a[tmp] - 1;
    ll ans = tmp;
    // cout << "loop=" << loop << endl; // loop+1で初めて被る。
    // cout << "tmp=" << tmp << endl;
    // cout << "mod=" << mod << endl;
    // cout << "k=" << k << endl;
    // for (int i = 0; i < n; i++)
    // {
    //     cout << b[i] << " ";
    // }
    // cout << endl;
    for (ll i = 0; i < k; i++)
    {
        ans = a[ans] - 1;
    }
    cout << ans + 1 << endl;

    return 0;
}

Measured memory_bytes: 6436
import std.stdio;
import std.conv;
import std.array;

void main()
{
    int N = readln.split[0].to!int;
    auto reader = readln.split;
    int[] A = new int[N + 1];
    for(uint i = 0; i < N + 1; i++){
        A[i] = reader[i].to!int;
    }
    reader = readln.split;
    int[] B = new int[N];
    for(uint i = 0; i < N; i++){
        B[i] = reader[i].to!int;
    }

    ulong ans = 0;
    for (uint i = 0; i < N; i++){
        ans += battle(A[i], B[i]);
        ans += battle(A[i + 1], B[i]);
    }
    
    writeln(ans);
}

int battle(ref int a, ref int b){
    int ret;

    if (b > a){
        ret = a;
        b -= a;
        a = 0;
    } else {
        ret = b;
        a -= b;
        b = 0;
    }
    
    return ret;
}


Measured memory_bytes: 9772
N,D=map(int,input().split())
X=[list(map(int,input().split())) for i in range(N)]
ans=0
for i in range(N-1):
  for j in range(1,N-i):
    L=0
    for k in range(D):
      L+=(X[i][k]-X[i+j][k])**2
    L=L**(0.5)
    if L.is_integer()==True:
      ans+=1
print(ans)

Measured memory_bytes: 3064