akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

#ifdef SG
	#include <debug.h>
#else
	#define show(...)
	#define debug(...)
	#define deepen(...)
	#define timer(...)
#endif

#define ARG4(_1,_2,_3,_4,...) _4

#define forn3(i,l,r) for (int i = int(l); i < int(r); ++i)
#define forn2(i,n) forn3 (i, 0, n)
#define forn(...) ARG4(__VA_ARGS__, forn3, forn2) (__VA_ARGS__)

#define ford3(i,l,r) for (int i = int(r) - 1; i >= int(l); --i)
#define ford2(i,n) ford3 (i, 0, n)
#define ford(...) ARG4(__VA_ARGS__, ford3, ford2) (__VA_ARGS__)

#define ve vector
#define pa pair
#define tu tuple
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define fs first
#define sc second
#define all(a) (a).begin(), (a).end()
#define sz(a) ((int)(a).size())

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int ui;
typedef unsigned char uc;
typedef pa<int, int> pii;
typedef pa<int, ll> pil;
typedef pa<ll, int> pli;
typedef pa<ll, ll> pll;
typedef ve<int> vi;

const ld pi = 3.1415926535897932384626433832795l;

template<typename T> inline auto sqr (T x) -> decltype(x * x) {return x * x;}
template<typename T1, typename T2> inline bool umx (T1& a, T2 b) {if (a < b) {a = b; return 1;} return 0;}
template<typename T1, typename T2> inline bool umn (T1& a, T2 b) {if (b < a) {a = b; return 1;} return 0;}

const int N = 100100;
int a[N];

int main () {
	cout.setf(ios::showpoint | ios::fixed);
	cout.precision(20);
#ifdef SG
	freopen((problemname + ".in").c_str(), "r", stdin);
//	freopen((problemname + ".out").c_str(), "w", stdout);
#endif
	int n, l;
	cin >> n >> l;
	forn(i, n)
		cin >> a[i];	
	int pos = -1;
	forn(i, n - 1) {
		if (a[i] + a[i + 1] >= l) {
			pos = i;
			break;
		}
	}
	if (pos < 0) {
		cout << "Impossible" << endl;
	} else {
		cout << "Possible" << endl;
		forn(i, pos) {
			printf("%d\n", i + 1);
		}
		ford(i, pos + 1, n - 1) {
			printf("%d\n", i + 1);
		}	
		printf("%d\n", pos + 1);
	}
	return 0;
}


Measured memory_bytes: 1280
# include<iostream>
# include<string.h>
using namespace std;

int main(void)
{
    std::ios::sync_with_stdio(false);
    char s[30];
    while(cin >> s && s!=NULL)
    {
        int a[30];
        int i, j = 0, k;
        memset(a, 0, sizeof(a));
        for(i = 0; s[i] != '\0'; ++i)
            a[s[i]-'a'] = 1;
        if(i == 26)
        {
          //  cout << "i=" << i << endl;
            for(j = i-1; j >= 0; --j)
            {
                char c;
                c = s[j]+1;
                for(; c <= 'z'; ++c)
                {
                //    cout <<s[j]<<" " <<c << endl;
                    if(a[c-'a'] == 0)
                    {
                        s[j] = c;
                        s[j+1] = '\0';
                        cout << s;
                        break;
                    }
                }

                a[s[j]-'a'] =0;
                if(c <= 'z')
                    break;
               // cout << s[j] <<" " <<a[s[j]-'a'] << endl;
            }
            //cout << "qq" << endl;
            if(j < 0)
                cout << "-1";
            cout << endl;
            continue;
        }
        for(j = i; j >= 0; --j)
        {
            char c;
            if(s[j] == '\0')
                c = 'a';
            else
                c = s[i] + 1;
            for(; c <= 'z'; ++c)
            {
                if(a[c-'a'] == 0)
                {
                    s[j] = c;
                    s[i+1] = '\0';
                    cout << s;
                    break;
                }
            }
            if(c <= 'z')
                break;
        }
        //cout << "qq" << endl;
        if(j < 0)
            cout << "-1";
        cout << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#define F first
#define S second

using namespace std;

typedef long long ll;

ll n;
ll a[2005];
pair<ll, ll> b[2005];
ll d[2005][2005];
ll ans;

int main()
{
    scanf("%lld", &n);
    for(ll i = 1; i <= n; i++)
    {
        scanf("%lld", &a[i]);
        b[i] = make_pair(a[i], i);
    }
    sort(b + 1, b + n + 1, greater<pair<ll, ll> >());
    for(ll i = 1; i <= n; i++)
    {
        for(ll j = 0; j <= i; j++)
        {
            if(j < i)d[i][j] = max(d[i][j], d[i - 1][j] + abs((n + 1 - (i - j)) - b[i].S) * b[i].F);
            if(j > 0)d[i][j] = max(d[i][j], d[i - 1][j - 1] + abs((j) - b[i].S) * b[i].F);
        }
    }
    for(ll j = 0; j < n; j++)
    {
        ans = max(ans, d[n][j]);
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 26464
import java.util.Scanner;

/**
 * @author hellb
 *
 */
public class Main {

	private static String ARC = "ARC";

	private static String ABC = "ABC";

	/**
	 * @param args
	 */
	public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);
        String sNum1 = scan.next();
        String sResult;
        scan.close();

        if (ARC.equals(sNum1)) {
        	sResult = ABC;
        } else {
        	sResult = ARC;
        }
        System.out.print(sResult);
	}
}


Measured memory_bytes: 26868
#define INF 2000000001
#define ll long long int
 
#include<bits/stdc++.h>
using namespace std;
 
void input(ll a[], ll n)
{
    for(ll i = 0; i < n; i++)
        cin >> a[i];
}
 
void print(ll a[], ll n)
{
    for(ll i = 0; i < n; i++)
        cout << a[i] << ' ';
    cout << '\n';
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    ll N, M;
    cin >> N >> M;
    cout << (M*(M - 1))/2 + (N*(N - 1))/2;
    
    return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>

#define fastio                              ios_base::sync_with_stdio(NULL); cin.tie(NULL); cout.tie(NULL);
#define read                                freopen("input.txt", "r", stdin);
#define write                               freopen("output.txt", "w", stdout);
#define nl                                  '\n'
#define mem(v,n)                            memset(v,n,sizeof(v))
#define debug(x)                            cerr << #x << " = " << x << nl
#define LCM(a,b)                            (a / __gcd(a,b) ) *b
#define GCD(a,b)                            __gcd(a,b)

#define ll                                  long long
#define ull                                 unsigned long long
#define vi                                  vector<int>
#define pb                                  push_back
#define vpii                                vector<pair<int, int>>
#define vpll                                vector<pair<ll, ll>>
#define mp                                  make_pair
#define ff                                  first
#define ss                                  second
#define all(v)                              v.begin(), v.end()
#define rsort(v)                            sort(v.rbegin(), v.rend())

using namespace std;

const double pi = 2*acos(0.0);



int main(){
    int n, p;
    cin >> n >> p;
    cout << n-p+1;
}















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

int main() {
  int A, B, C;
  cin >> A >> B >> C;
  if ( A + B >= C ) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}


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

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

    int n;
    cin >> n;
    vector<int> a;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if (x % 2 == 0) {
            a.push_back(x);
        }
    }

    for (int i = 0; i < (int) a.size(); i++) {
        if ((a[i] % 3 != 0 && a[i] % 5 != 0)) {
            cout << "DENIED\n";
            return 0;
        }
    }

    cout << "APPROVED\n";
    return 0;
}


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

#define NEW(p,n){p=malloc((n)*sizeof(p[0]));if(p==NULL){printf("not enough memory\n");exit(1);};}
//pの型の変数n個の要素分のメモリを確保し、そのアドレスをpに代入するマクロ

#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define SWAP(type, x, y) do { type tmp = x; x = y; y = tmp; } while (0)

#define MOD 1000000007 

typedef struct{
    int priority;
    double value;
}data;

//昇順
int asc(const void* a, const void* b){
    return *(int*)a-*(int*)b;
}

//降順
int desc(const void* a, const void* b){
    return *(int*)b-*(int*)a;
}

int main(void){
    char S[4];
    scanf("%s",S);

    if(S[0]=='S'){
        if(S[1]=='U') printf("7\n");
        else printf("1\n");
    }
    else if(S[0]=='M') printf("6\n");
    else if(S[0]=='T'){
        if(S[1]=='U') printf("5\n");
        else printf("3\n");
    }
    else if(S[0]=='W') printf("4\n");
    else printf("2\n");

    return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int a,b,c,n,ans=0;
int main(){
    cin>>a>>b>>c>>n;
    for (int i=0;i<=a;i++){
    	for (int j=0;j<=b;j++){
    		if ((n-i*500-j*100>=0)&&(n-i*500-j*100<=c*50)){
    			ans++;
			} 
		}
      
	}
     
    cout<<ans;
    return 0;
}

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

typedef long long ll;

using namespace std;

int main() {
    int n = 5;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        if (x == 0) {
            cout << i << endl;
        }
    }
    return 0;
}



Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
int main() {
    int N;
    cin >> N;
    vector<double> v(N);
    for(int i = 0; i < N; i++) {
        cin >> v.at(i);
    }

    sort(v.begin(), v.end());

    for(int i = 0; i < N-1; i++) {
        v.at(i+1) = (v.at(i) + v.at(i+1)) / 2.0;
    }

    cout << v.at(N-1) << endl;
}

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

using namespace std;
int main()

{
  string s;

  cin>>s;

  if(s[0]==s[1]||s[1]==s[2]||s[2]==s[3]){
    cout<<"Bad"<<endl;
  }

  else {
    cout<<"Good"<<endl;
  }

return 0;

}

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

int main()
{
    int n, a[4001], b[4001];
    double* d;

    cin >> n;

    d = new double[n];

    for( int i = 0; i < 4001; i++ )
    {
        a[i] = 0;
        b[i] = 0;
    }

    for( int i = 0; i < n; i++ )
    {
        cin >> d[i];
        int c = (int)( 1000 * ( d[i] + 0.0004 ) );
        a[c]++;
    }

    for( int i = 1; i < 4001; i++ )
        b[i] = b[i-1] + a[i-1];

    for( int i = 0; i < 4001; i++ )
    {
        if( a[i] > 1 )
            b[i] = a[i] - 1 + b[i] * 3;
        else
            b[i] = b[i] * 3;
    }

    for( int i = 0; i < n; i++ )
        cout << b[(int)(1000*(d[i]+0.0004))] << endl;

    delete d;
    return 0;
}


Measured memory_bytes: 3660
N,M=map(int,input().split())
n = [0]*(M+1)
for i in range(N):
  K,*A=map(int,input().split())
  for j in range(K):
    n[A[j]] += 1

count = 0
for i in range(len(n)):
  if n[i]==N:count += 1

print(count)

Measured memory_bytes: 9172
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <map>

using ll = long long;

using namespace std;

int main() {
    long n, k;
    cin >> n >> k;
    long rui[n+1];
    rui[0] = 0;
    for (int i=0; i<n; i++) {
        long ai; cin >> ai;
        rui[i+1] = (rui[i] + ai) % k;
    }
    map<long, long> acnt;
    long ans=0;
    for (long i=0; i<=n; i++) {
        if (i >= k) acnt[(i + k - rui[i-k]) % k]--;
        long r = (i + k - rui[i]) % k;
        ans += acnt[r];
        // cerr << i << ' ' << rui[i] << ' ' << r << ' ' << acnt[r] << '\n';
        acnt[r]++;
    }
    cout << ans << '\n';
    return 0;
}

Measured memory_bytes: 14336
#include <stdio.h>
int main(){
	int a[4][3][10], i, j, k, n, b, f, v, r;
	for (i = 0; i<4; i++)
	{
		for (j = 0; j<3; j++)
		{
			for (k = 0; k<10; k++)
			{
				a[i][j][k] = 0;
			}
		}
	}
	scanf("%d\n", &n);
	for (i = 0; i<n; i++)
	{
		scanf("%d %d %d %d\n", &b, &f, &r, &v);
		a[b - 1][f - 1][r - 1] += v;
	}
	for (i = 0; i<4; i++)
	{
		for (j = 0; j<3; j++)
		{
			for (k = 0; k<10; k++)
			{
				printf(" %d", a[i][j][k]);
				if (k == 9)printf("\n");
				if (k == 9 && j == 2 && i<3)printf("####################\n");
			}
		}
	}
	return 0;
}


Measured memory_bytes: 2040
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
  int N;
  cin >> N;
  for (int n = 0; n < N; ++n) {
    string A, B;
    cin >> A >> B;

    int A_size = A.size(), B_size = B.size(),
        ans_size = max(A_size, B_size) + 1;
    vector<int> ans(ans_size);
    for (int i = A_size - 1; i >= 0; --i)
      ans[ans_size - A_size + i] = A[i] - '0';
    for (int j = B_size - 1; j >= 0; --j) {
      ans[ans_size - B_size + j] += B[j] - '0';
      for (int k = ans_size - 1; k > 0; --k)
        if (ans[k] >= 10)
          ans[k] -= 10, ++ans[k - 1];
    }

    if (A_size > 80 || B_size > 80 || (ans_size == 81 && ans[0] != 0) ||
        ans_size > 81) {
      cout << "overflow" << endl;
    } else {
      for (int i = 0; i < ans_size; ++i) {
        if (i == 0 && ans[i] == 0)
          continue;
        cout << ans[i];
      }
      cout << endl;
    }
  }
}


Measured memory_bytes: 3080
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
    int n, m, x, y;
    cin >> n >> m >> x >> y;
    vector<int> xcity(n), ycity(m);
    for (int i = 0; i < n; i++)
    {
        cin >> xcity.at(i);
    }
    for (int i = 0; i < m; i++)
    {
        cin >> ycity.at(i);
    }
    int maxx = *max_element(xcity.begin(), xcity.end());
    int miny = *min_element(ycity.begin(), ycity.end());
    bool flag = false;
    for (int i = maxx + 1; i <= miny; i++)
    {
        if (i > x && i <= y)
        {
            flag =true;
            break;
        }
    }
    if (flag) {
        cout << "No War" << endl;
    }
    else
    {
        cout << "War" << endl;
    }
    
}

Measured memory_bytes: 256
#include <iomanip>
#include <iostream>
#include <vector>
#define rep(i, n) for (int i = 0; i < (n); i++)
typedef long long ll;
using namespace std;

int main(void) {
  ios::sync_with_stdio(false);
  int N;
  cin >> N;
  vector<int> P(N);
  rep(i, N) cin >> P[i];

  int ans = 1;
  int minNum = P[0];
  for (int i = 1; i < N; ++i) {
    if (minNum >= P[i]) ans++;
    minNum = min(minNum, P[i]);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1024
#include<stdio.h>

int mat[9][9],check1[9][9],check2[9][9],check3[9][9],flag[9];

void reflesh(int *flag);
void c_check();
void d_check();
void mass_check(int x,int y);

int main(void){
  int set;
  int i,j,k;
  scanf("%d",&set);
  do{
    for(i=0;i<9;i++){
      for(j=0;j<9;j++){
	scanf("%d",&mat[i][j]);
	check1[i][j]=0;
	check2[i][j]=0;
	check3[i][j]=0;
      }
    }
    reflesh(flag);
    c_check();
    d_check();
    for(i=0;i<9;i+=3){
      for(j=0;j<9;j+=3){
	mass_check(i,j);
      }
    }
    for(i=0;i<9;i++){
      for(j=0;j<9;j++){
	if(check1[i][j]!=0||check2[i][j]!=0||check3[i][j]!=0) printf("*%d",mat[i][j]);
	else printf(" %d",mat[i][j]);
      }
      putchar('\n');
    }
    if(set-1!=0) putchar('\n');
  }while(--set);
  return 0;
}

void reflesh(int *array){
  int a;
  for(a=0;a<9;a++){
    array[a]=0;
  }
}

void c_check(){
  int a,b;
  for(a=0;a<9;a++){
    for(b=0;b<9;b++){
      //printf("(%d,%d) %d\n",a,b,flag[mat[a][b]-1]);
      if(flag[mat[a][b]-1]==0){
	flag[mat[a][b]-1]+=b+1;
      }else{
	check1[a][b]++;
	check1[a][flag[mat[a][b]-1]-1]++;
      }
    }
    reflesh(flag);
  }
}

void d_check(){
  int a,b;
  for(a=0;a<9;a++){
    for(b=0;b<9;b++){
      //printf("(%d,%d) %d\n",a,b,flag[mat[b][a]-1]);
      if(flag[mat[b][a]-1]==0){
	flag[mat[b][a]-1]+=b+1;
      }else{
	check2[b][a]++;
	check2[flag[mat[b][a]-1]-1][a]++;
      }
    }
    reflesh(flag);
  }
}

void mass_check(int x,int y){
  int a,b,c,d;
  for(a=x;a<x+3;a++){
    for(b=y;b<y+3;b++){
      //printf("now=%d\n",(a-x)*3+(b-y)+1);
      //printf("(%d,%d) %d\n",a,b,flag[mat[a][b]-1]);
      if(flag[mat[a][b]-1]==0){
	flag[mat[a][b]-1]+=(a-x)*3+(b-y)+1;
	//printf("flgnum=%d,%d\n",mat[a][b]-1,flag[mat[a][b]-1]);
      }else{
	for(c=x;c<x+3;c++){
	  for(d=y;d<y+3;d++){
	    if(mat[c][d]==mat[a][b]){
	      check3[c][d]++;
	    }
	  }
	}
      }
    }
  }
  reflesh(flag);
}

Measured memory_bytes: 0
#include <iostream>

using namespace std;

int main()
{
   long long int h,n;
   cin>>h>>n;
   long long int a[n+1];
   long long int sum=0;
   for(int i=1;i<=n;i++)
   {
       cin>>a[i];
       sum=sum+a[i];
   }
   if(h-sum>0)
    cout<<"No";
    else
    cout<<"Yes";
    return 0;
}


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

int main() {
    int N=0;
    cin >> N;
    int ans=0;
    vector<int> H(N);
    bool all0 = true;
    for(int i=0; i<N; i++){
        cin >> H[i];
        if(H[i] != 0)all0 = false;
    }
    if(all0){
        cout << 0 << endl;
        return 0;
    }
    while(1){
        int i=0;
        bool first=true,end=false;
        while(i<H.size() && !end){
            if(H[i]==0){
                if(!first){
                    end = true;
                }
                i++;
            }else{
                first = false;
                H[i] -= 1;
                i++;
            }
        }
        ans += 1;
        bool finish=true;
        for(int j=0; j<H.size() && finish != false; j++){
            if(H[j] != 0){finish = false;}
        }
        if(finish)break;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
n = int(input())
l = list(map(int, input().split()))
c_dic={}
for i in l:
    if i in c_dic:
        c_dic[i]+=1
    else:
        c_dic[i]=1
c_l=[]
for i,j in c_dic.items():
    if j>=2:
        c_l.append(i)
    if j>=4:
        c_l.append(i)
c_l.sort(reverse=True)
if len(c_l)<2:
    print(0)
else:
    print(c_l[0]*c_l[1])


Measured memory_bytes: 18060
import Control.Applicative
import Control.Monad

main :: IO ()
main = do
  [n, m] <- f
  unless (n == 0 && m == 0) $ do
    solve <$> replicateM n g <*> replicateM m getLine >>= print
    main
  where
    f = map read <$> words <$> getLine
    g = (\[a, b] -> (a, read b)) <$> words <$> getLine

solve :: [(String, Int)] -> [String] -> Int
solve xs ys = sum $ do
  (as, p) <- xs
  bs <- ys
  guard $ and $ zipWith f as bs
  return p
  where
    f a b = a == '*' || a == b



Measured memory_bytes: 5548
#include <stdio.h>
 
int sol(int,int);
 
int A[2001],m[2001];
 
int n;
 
int main(){
  int i,j,q;
 
  scanf("%d", &n);
  for(i=0; i<n; i++) {
    scanf("%d", &A[i]);
  }
  scanf("%d",&q);
  for(i=0; i<q; i++) {
    scanf("%d", &m[i]);
  }
 
  for(i=0;i<q;i++){
    if(sol(0,m[i]))printf("yes\n");
    else printf("no\n");
  }
  
  return 0;
}
 
int sol(int x, int y){
 
  if(A[x] == y)return 1;
 
  if(x+1  == n)return 0;
 
  if(sol(x+1,y-A[x]) || sol(x+1,y))return 1;
  return 0;
 }

Measured memory_bytes: 584
use proconio::input;

#[allow(unused_imports)]
use proconio::marker::{Bytes, Chars, Usize1};
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
#[allow(unused_imports)]
use std::ops::*;

#[derive(Clone, Debug, Default, PartialEq, Eq, PartialOrd, Ord)]
struct Struct;

//#[proconio::fastout]
fn main() {
    input! {
        n: usize,
        p: usize,
        s: Bytes,
    }

    let mut ans = 0u64;
    if p == 2 || p == 5 {
        for i in 0..n {
            if (s[i] - b'0') as usize % p == 0 {
                ans += i as u64 + 1;
            }
        }
    } else {
        // hist[i] : s[j]以降を整数とみなしたとき値 % P == i となるjの値が何個あるか
        // 0<=j<=n
        let mut hist = vec![0; p];
        hist[0] = 1;
        let mut val = 0;
        let mut mul = 10;
        for i in (0..n).rev() {
            val = ((s[i] - b'0') as usize * mul + val) % p;
            mul = mul * 10 % p;
            hist[val] += 1;
        }
        for i in 0..p {
            let x = hist[i];
            if x > 0 {
                ans += x * (x - 1) / 2;
            }
        }
    }

    println!("{}", ans);
}


Measured memory_bytes: 2432
#Lupin The 4th: O(2^n)
def f(a, b, visited):
    w = W[visited] * 20
    return float(abs(lengths[a] - lengths[b])) / (2000. / (70 + w))

def solve():
    cache = dict([((i, 0), (0., [i])) for i in xrange(n)])
    def dfs(top, visited):
        if (top, visited) in cache:
            return cache[(top, visited)]
        ret = (1 << 30, [-1])
        for i in xrange(n):
            if (visited >> i) & 1 == 1:
                tmp = dfs(i, visited ^ (1 << i))
                c = tmp[0] + f(top, i, visited)
                if c < ret[0]:
                    ret = (c, tmp[1])
        cache[(top, visited)] = (ret[0], ret[1] + [top])
        return cache[(top, visited)]
    mask = (1 << n) - 1
    ret = (1 << 30, -1)
    for i in xrange(n):
        ret = min(ret, dfs(i, mask ^ (1 << i)))
    return ret[1]

n = input()
num, lengths, weights = zip(*[map(int, raw_input().split()) for _ in xrange(n)])
cache = dict([((i, 0), 0) for i in xrange(n)])
W = [0] + [sum(weights[i] for i in xrange(n) if (b >> i) & 1 == 1)  
           for b in xrange(1, 1 << n)]
print " ".join(map(lambda i:str(num[i]), solve()))

Measured memory_bytes: 100912
//g++ -std=c++14 test.cpp -o test.out
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <cassert>
#include <algorithm>
#include <functional>
#include <iostream>
#include <iomanip>
#include <vector>
#include <queue>
#include <map> 
#include <utility>
using namespace std;

int N;
int P = 0;
int Q = 0;
int ans;

int table[40320];//小さい順に数を格納
int table_length = 0;

int digit_table[8];//digit_table[i]=10のi乗

void make_digit_table(){
  digit_table[0] = 1;
  for(int i=1;i<8;i++) digit_table[i]=digit_table[i-1]*10;
}

void init(int num,int sum,int digit,int checkbit){
  //1~8の数numを、digit桁目に配置する
  //checkbitのi桁目が立っている==iはもう使った
  for(int i=1;i<=N;i++){//iをdigit桁目に付加する
      if(!((checkbit>>(num-1))&0x1)){
        if(digit==1){
          table[table_length] = sum+num;
          //cout << table_length << ':' << table[table_length] << endl;
          table_length++;
          return;
        }
        init(i,sum+num*digit_table[digit-1],digit-1,checkbit|(0x1<<(num-1)));
      }
  }
}
 
void solve(){
  for(int i=1;i<=N;i++) init(i,0,N,0);
  sort(table,table+table_length);
  int a,b;
  for(int i=0;i<table_length;i++){
    if(table[i]==P){
      a = i+1;
      //cout << "a:" << a << endl;
      break;
    }
  }
  for(int i=0;i<table_length;i++){
    if(table[i]==Q){
      b = i+1;
      //cout << "b:" << b << endl;
      break;
    }
  }
  ans = abs(a-b);
}
 
int main(){
  make_digit_table();
  cin>>N;
  for(int i=N-1;i>=0;i--){
    int p;
    cin>>p;
    P = P+p*digit_table[i];
  }
  for(int i=N-1;i>=0;i--){
    int q;
    cin>>q;
    Q = Q+q*digit_table[i];
  }
 
	solve();

  cout<<ans;
  return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
const int N = 2e5+10;
const int M =1e9+7;
#define int long long int
using namespace std;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define MAX 1e15+1
#define pi  pair<int,int>




int a[4];

signed main(){
    fast;
   int a,b;
   cin>>a>>b;
   int x=__gcd(a,b);
   cout<<(a*b)/x ;

  return 0;



    
 
    
 
 
}



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

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

    long long A[N], sums;

    sums = 1;
    long long res = 0;
    for(int i=0;i<N;i++){
        cin >> A[i];
        while(A[i]%2 == 0){
            A[i] = A[i] / 2;
            res++;
        }
    }

    cout << res << endl;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define pll pair<ll,ll>
#define pii pair<int,int>
#define rep(i,n) for(int i=0;i<n;i++)
#define For(i,a,b) for(int i=a;i<b;i++)
#define sz(x) ((ll)(x).size())
#define pb push_back
#define mp make_pair
#define bit(n) (1LL<<(n))
#define F first
#define S second
#define debug(x) cerr << x << endl
#define Complex complex<double>
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
const ll INF = 1LL<<60;
const ll mod = (int)1e9 + 7;

int main() {
    int n;
    cin >> n;
    int l[n];
    rep(i,n)cin >> l[i];
    int cnt=0;
    rep(i,n){
        rep(j,i){
            rep(k,j){
                if(l[i]==l[j] || l[j]==l[k] || l[k]==l[i])continue;
                if(max({l[i],l[j],l[k]})<l[i]+l[j]+l[k]-max({l[i],l[j],l[k]}))cnt++;
            }
        }
    }
    cout << cnt;

    
}

Measured memory_bytes: 3616
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;
const ll inf = (1 << 30) - 1;
const ll infll = (1LL << 61) - 1;

ll gcd(ll a, ll b) { return (b ? gcd(b, a % b) : a); }
ll lcm(ll a, ll b) { return a / (gcd(a, b)) * b; }

template <typename T>
void print(vector<T> vec)
{
    int n = vec.size();
    for (int i = 0; i < n; i++)
    {
        cout << vec[i] << (i == n - 1 ? "\n" : " ");
    }
}

int N;

int main()
{
    cin >> N;
    vector<ll> A(N);
    for (int i = 0; i < N; i++)
    {
        cin >> A[i];
    }
    vector<ll> left(N + 1), right(N + 1);
    left[0] = A[0], right[N] = A[N - 1];
    for (int i = 0; i < N; i++)
    {
        left[i + 1] = gcd(A[i], left[i]);
        right[N - i - 1] = gcd(A[N - 1 - i], right[N - i]);
    }
    ll ans = left[N - 1];
    right[N] = A[0], left[0] = A[N - 1];
    //print(left);  //A[0]~A[i-1]
    //print(right); //A[i]~A[N-1]
    for (int i = 1; i < N; i++)
    {
        ans = max(ans, gcd(left[i - 1], right[i]));
    }
    cout << ans << endl;
}

Measured memory_bytes: 2560
using System;

namespace tst
{
    class Program
    {
        public static void Main()
        {
            string[] In = Console.ReadLine().Split(' ');
            int h = int.Parse(In[0]);
            int w = int.Parse(In[1]);
            long res = 0;
            if (h == 1 || w == 1)
            {
                res = 1;
            }
            else
            {
                if(h % 2 == 0)
            {
                    long temp = h / 2;
                    res = temp * w;
                }
            else
                {
                    if (w % 2 == 0)
                    {
                        long temp = w / 2;
                        res = temp * h;
                    }
                    else
                    {
                        int hp = h / 2;
                        int wp = w / 2;
                        int sub = hp + wp + 1;
                        h++;
                        w++;
                        long temp = w / 2;
                        res = temp * h - sub;
                    }
                }
            }
            Console.WriteLine(res);
        }
    }
}

Measured memory_bytes: 13140
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define INF (1LL<<50)
#define MOD 1000000007

int main(){
    ll N;
    ll ans = 0;
    cin >> N;
    for(int i=1;i<=N;i++){
        if(!(i%3==0||i%5==0)){
            ans+=i;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3636
import java.util.Scanner;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        double A = sc.nextInt();
        double B = sc.nextInt();
        double H = sc.nextInt();
        double M = sc.nextInt();
        double ans;
        
        double sho = (H * 60 + M) * 360 / ( 12 * 60 );
        double lon = M * 360 / 60;
        double ang;
        
        ang = Math.abs(sho - lon);
        
        ans = Math.sqrt(A * A + B * B 
                - 2.0 * A * B * Math.cos(Math.toRadians(ang)));
        
        System.out.print(ans);
    }
}

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

int main(){
    string alphabet[26]={"a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"};
    string s;
    cin >> s;
    for(int i=0;i<26;i++){
        if(s==alphabet[i])cout << alphabet[i+1] << endl;
    }
}

Measured memory_bytes: 256
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_imports)]
use std::{i32, i64, u32, u64, f64};
#[allow(unused_imports)]
use std::cmp::{max, min, Ordering};
#[allow(unused_imports)]
use std::collections::{VecDeque, HashMap, BTreeMap, HashSet, BTreeSet};
#[allow(unused_imports)]
use std::io::{stdout, Write, BufWriter};
#[allow(unused_imports)]
use std::mem::{swap};

fn main() {
    input!{
        i: i64,
        o: i64,
        _t: i64,
        j: i64,
        l: i64,
        _s: i64,
        _z: i64,
    }
    let ijl = [i, j, l];
    let s = ijl.iter().sum::<i64>();
    if ijl.iter().all(|x| x % 2 == 0)
        || ijl.iter().all(|x| x % 2 == 1) { println!("{}", o + s); }
    else if s == 2 { println!("{}", o); }
    else { println!("{}", o + s - 1); }
}


Measured memory_bytes: 4476
import java.util.Scanner;

public class Main {
	static int ans;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = Integer.parseInt(sc.next());
		
		gcd(n);
		System.out.println(ans);

	}
	
	static void gcd(int x) {
		boolean jdg = true;
		for(int i = 2 ; i * i <= x ;i++) {
			if(x % i == 0) {
				jdg = false;
				break;
			}
		}
		if(jdg) {
			ans = x;
			return;
		}
		gcd(x+1);
	}

}


Measured memory_bytes: 23764
program main
  implicit none
  integer(8) :: n, k, mi, ma, md, i
  integer(8), allocatable :: a(:)
  read *, n, k
  allocate (a(n))
  read *, a(:)
  call quicksort(a)

  ! 積がthres以下になるペアがk個以上ある最小のthres
  mi = -2 * 10_8 ** 18  ! NG
  ma = 2 * 10_8 ** 18  ! OK
  do i = 1, 70
    md = mi + (ma - mi) / 2
    if (isok(md)) then
      ma = md
    else
      mi = md
    end if
  end do

  print "(i0)", ma

  contains

  logical function isok(x)
    ! 積がx以下になるペアがk個以上ある
    integer(8), intent(in) :: x
    integer(8) :: i, cnt
    cnt = 0
    do i = 1, n
      cnt = cnt + count_lower(i, x)
    end do
    isok = (cnt >= k)
  end function isok

  integer(8) function count_lower(i, x)
    ! a(i) * a(j) <= x となるj>iの数
    integer(8), intent(in) :: i, x
    integer(8) :: j, mi, md, ma
    if (a(i) >= 0) then
      ! a(i) * a(j) <= x となる最大のjを求める
      mi = i  ! ok
      ma = n + 1  ! ng
      do j = 1, 30
        md = mi + (ma - mi) / 2
        if (a(i) * a(md) <= x) then
          mi = md
        else
          ma = md
        end if
        if (ma - mi <= 1) exit
      end do
      count_lower = mi - i
    else
      ! count_lower = 0
      ! do j = i + 1, n
      !   if (a(i) * a(j) <= x) count_lower = count_lower + 1
      ! end do

      ! a(i) * a(j) <= x となる最小のjを求める
      mi = i  ! ng
      ma = n + 1  ! ok
      do j = 1, 30
        md = mi + (ma - mi) / 2
        if (a(i) * a(md) <= x) then
          ma = md
        else
          mi = md
        end if
        if (ma - mi <= 1) exit
      end do
      count_lower = n - (ma - 1)
    end if
  end function count_lower

  recursive subroutine quicksort(a)
    integer(8), intent(inout) :: a(:)
    integer(8) :: pivot, i, j, k, tmp, n
    real(8) :: r
    n = size(a)
    if (n <= 1) return
    i = 1
    j = n
    call random_number(r)
    k = 1 + floor(r * n)
    k = max(1_8, min(k, n))
    pivot = a(k)
    do
      do while (.not. pivot <= a(i))
        i = i + 1
      end do
      do while (.not. a(j) <= pivot)
        j = j - 1
      end do
      if (i >= j) exit
      tmp = a(i)
      a(i) = a(j)
      a(j) = tmp
      i = i + 1
      j = j - 1
    end do
    call quicksort(a(1:i - 1))
    call quicksort(a(j + 1:n))
  end subroutine quicksort
end program main


Measured memory_bytes: 2304
#include <bits/stdc++.h>
using namespace std;
int main() {
  int a, b, c;
  cin >> a >> b >> c;

  if (a == b && b != c) {
    cout << "Yes" << endl;
  }
  else if (b == c && a != c) {
    cout << "Yes" << endl;
  }
  else if (a == c && a != b) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
def main():
    n = int(input())
    val = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
    print(val[n-1])

if __name__ == '__main__':
    main()

Measured memory_bytes: 38504
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#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 <regex>
#define rep(i,n) for(int i = 0; i < n; i++)
#define reps(i,j,n) for(int i = j; i < n; i++)
#define rrep(i,j,n) for(int i = j-1; i >= n; i--)
#define prec(n) fixed << setprecision(n)
#define print_array(v) rep(__k, v.size()) { cout << v[__k]; if(__k != v.size()-1) cout << " "; else cout << endl; }
#define YesorNo(a) printf(a?"Yes\n":"No\n")
#define fi first
#define se second
using namespace std;

int inf = 2147483647;
int64_t inf64 = 9223372036854775807;
int mod = 1e+7;

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

  int n;
  cin >> n;

  int res = 0;
  while(n--) {
    int a;
    cin >> a;
    res += a-1;
  }
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
    int N, T, min = 1000, cost = 1000, TLE = 0;
    cin >> N >> T;
    int c[N], t[N];
    for (int i = 0; i < N; i++) {
        cin >> c[i] >> t[i];
        if (T >= t[i]) {
            if (min >= c[i] && cost > c[i]) {
                cost = c[i];
            }
        } else {
            TLE++;
        }
    }
    if (TLE == N) {
        cout << "TLE" << endl;
    } else {
        cout << cost << endl;
    }
}

Measured memory_bytes: 256
// Aizu 1104: Where's Your Robot?
// 2017.9.12 bal4u@uu

#include <stdio.h>

#define N 0
#define E 1
#define S 2
#define W 3
int r90[4] = { E, S, W, N };
int l90[4] = { W, N, E, S };
int f[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
int b[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };

int main()
{
	int w, h, r, c, d, r2, c2, k;
	char buf[20], cmd;

	while (scanf("%d%d", &w, &h) && w) {
		r = 1, c = 1, d = N;
		while (1) {
			scanf("%s", buf), cmd = *buf; 
			if      (cmd == 'S') break;
			else if (cmd == 'R') d = r90[d];
			else if (cmd == 'L') d = l90[d];
			else { scanf("%d", &k);
				if (cmd == 'F') r2 = r + k*f[d][1], c2 = c + k*f[d][0];
				else			r2 = r + k*b[d][1], c2 = c + k*b[d][0];
				if (r2 < 1) r2 = 1; if (r2 > h) r2 = h;
				if (c2 < 1) c2 = 1; if (c2 > w) c2 = w;
				r = r2, c = c2;
			}
		}
		printf("%d %d\n", c, r);
	}
	return 0;
}

Measured memory_bytes: 1756
package main

import (
	"fmt"
)

func main() {
	var (
		a, b int
		s    string
	)
	fmt.Scan(&a, &b, &s)

	for i := 0; i < a; i++ {
		if !('0' <= s[i] && s[i] <= '9') {
			fmt.Println("No")
			return
		}
	}
	if s[a] != '-' {
		fmt.Println("No")
		return
	}
	for i := a + 1; i <= a+b; i++ {
		if !('0' <= s[i] && s[i] <= '9') {
			fmt.Println("No")
			return
		}
	}
	fmt.Println("Yes")
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define ll long long
#define P pair<int,int>
#define fast_io ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
const int MOD = 1000000007;
const int INF = 2002002002;
const ll LLINF = 9009009009009009009;
using namespace std;

int main() {
    fast_io
    const int N_ALPHA = 26;
    vector<vector<int>> alp(N_ALPHA);
    string s, t;
    cin >> s >> t;

    rep(i,s.size()) alp[s[i]-'a'].push_back(i+1);

    ll n = s.size(), ans = 0;;
    int f_ind, c_ind = 0;
    for (char c: t) {
        f_ind = c_ind;
        if (alp[c-'a'].empty()) {cout << -1 << endl; return 0;}
        if (alp[c-'a'].end() - upper_bound(alp[c-'a'].begin(), alp[c-'a'].end(), f_ind) == 0) c_ind = alp[c-'a'][0];
        else c_ind = *upper_bound(alp[c-'a'].begin(), alp[c-'a'].end(), f_ind);
        if (f_ind < c_ind) ans += (c_ind - f_ind);
        else ans += (n - f_ind) + c_ind;
    }
    
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1228
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    int a[n+1][3];
    for(int i=1;i<=n;i++){
        for(int j=0;j<3;j++){
            cin>>a[i][j];
        }
    }
    int dp[n+1][3];
    dp[1][0]=a[1][0];
    dp[1][1]=a[1][1];
    dp[1][2]=a[1][2];
    for(int i=2;i<=n;i++){
        dp[i][0]=a[i][0]+max(dp[i-1][1],dp[i-1][2]);
        dp[i][1]=a[i][1]+max(dp[i-1][2],dp[i-1][0]);
        dp[i][2]=a[i][2]+max(dp[i-1][1],dp[i-1][0]);
    }
    cout<<max(dp[n][0],max(dp[n][1],dp[n][2]));
}

Measured memory_bytes: 5956
import sys
from collections import defaultdict
from heapq import heappop, heappush
N, M = map(int, sys.stdin.readline().split())
A = defaultdict(list)
for line in sys.stdin:
    a, b = map(int, line.split())
    if a <= M:
    	A[M-a].append(b)

ans = 0
q = []
for i, B in sorted(A.items()):
    for b in B:
        heappush(q, b)
        ans += b
    while len(q) > i+1:
        b = heappop(q)
        ans -= b
print(ans)


Measured memory_bytes: 36900
#include <bits/stdc++.h>
#include <ext/algorithm>
#include <ext/numeric>

using namespace std;
using namespace __gnu_cxx;

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

/**************************************************************/

	int N, M, xi, yi, count = 1;	//xi = source_box, yi = destination_box
	cin >> N >> M;
	int balls_amount_in_box[N];
	bool red_ball_might_be_in_box[N];

	balls_amount_in_box[0] = 1;
	red_ball_might_be_in_box[0] = true;
	for(int i = 1; i < N; i++)
	{
		balls_amount_in_box[i] = 1;
		red_ball_might_be_in_box[i] = false;
	}

	while(M-- > 0){
		cin >> xi >> yi;
		xi--; yi--;	//0-based indexes
		/*According to the problem, just before the i-th operation is performed, box xi contains at least 1 ball. 
		That means that, after doing the operation "balls_amount_in_box[xi]--;", the value in that box will be 
		greater or equal than 0, so there's no need	to be careful about getting negative values in a box.*/
		balls_amount_in_box[xi]--;
		balls_amount_in_box[yi]++;

		if(red_ball_might_be_in_box[xi])
		{
			if(!red_ball_might_be_in_box[yi])
			{
				red_ball_might_be_in_box[yi] = true;
				count++;
			}
			if(balls_amount_in_box[xi] == 0)
			{
				red_ball_might_be_in_box[xi] = false;
				count--;
			}
		}
	}

	cout << count << endl;
}



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

int main() {

int x;
  cin >> x;
  int number = 1;

  for (int i = 1; i < 32; i++){
    for (int j =2; j < 10; j++){
      if(pow(i,j)<=x && number < pow(i,j)) { number = pow(i,j);}
    }
  }

  cout << number << endl;
}


Measured memory_bytes: 512
#!/usr/bin/env python3

def solve_m(S, T, K):
    def count(x):
        ret, ti = 0, 0
        for s in S:
            # 積がxを初めて下回るtiを求める。なければlen(T)
            while ti < len(T) and s * T[ti] > x:
                ti += 1
            if ti == len(T):
                break
            ret += len(T) - ti
        return ret
    left, right = -(10**18)-1, 10**18+1
    while abs(right - left) > 1:
        mid = (left + right) // 2
        if count(mid) < K:
            left = mid
        else:
            right = mid
    return right

def solve(S, mS, K):
    def count(x, T):
        ret, j = 0, len(T) - 1
        for i, t in enumerate(T):
            while j >= 0 and t * T[j] > x:
                j -= 1
            if j == -1:
                break
            ret += j + 1 - (1 if i <= j else 0)
        return ret // 2
    left, right = -(10**18)-1, 10**18+1
    while abs(right - left) > 1:
        mid = (left + right) // 2
        if count(mid, S) + count(mid, mS) < K:
            left = mid
        else:
            right = mid
    return right

def main():
    N, K = list(map(int, input().split()))
    A = sorted(map(int, input().split()), reverse=True)
    B = {-1:[], 0:[], 1:[]}
    for a in A:
        if a == 0:
            B[0].append(0)
        else:
            B[a//abs(a)].append(a)
    m = len(B[-1]) * len(B[1])
    z = len(B[0]) * (N-len(B[0])) + len(B[0]) * (len(B[0])-1) // 2
    if K <= m:
        print(solve_m(B[1], B[-1], K))
    elif K <= m + z:
        print(0)
    else:
        print(solve(sorted(B[1]), B[-1], K - m - z))


if __name__ == '__main__':
    main()


Measured memory_bytes: 95700
import java.util.*;

public class Main {
    static Scanner sc = new Scanner(System.in);
    static int[] dp;
    static int n, x;
    static int[] value;
    static boolean[] prime;
    public static void main(String[] args) {
        makePrime();
        while(read()){
            solve();
        }

    }

    static void makePrime(){
        prime = new boolean[1000001];
        Arrays.fill(prime, true);
        prime[0] = false;
        prime[1] = false;
        for(int i = 2; i < prime.length; i++){
            if(prime[i]){
                for(int j = i*2; j < prime.length; j += i)prime[j] = false;
            }
        }
    }

    static boolean read(){
        n = sc.nextInt();
        x = sc.nextInt();
        if( n == 0 && x == 0)return false;

        dp = new int[x+1];
        value = new int[n];

        for(int i = 0; i < value.length; i++){
            value[i] = sc.nextInt();
        }

        return true;
    }

    static void solve(){
        boolean f = false;
        int max = 0;

        for(int i = 0; i < n; i++){
            for(int j = value[i]; j <= x; j++){

                dp[j] = Math.max(dp[j], dp[j - value[i]] + value[i] );

                int k = dp[j];
                if(prime[k]){
                    max = k;
                    f = true;
                }

            }
        }

        if(f){
            System.out.println(max);
        }else{
            System.out.println("NA");
        }

    }
}

Measured memory_bytes: 22000
#include <bits/stdc++.h>
#define PB push_back
#define MP make_pair
#define REP(i,n) for (int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define ALL(a) (a).begin(),(a).end()
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
const int INF=1e9;
char fld[1010][1010];
char flg[2][2];
string tmp="JOI";
int m,n;
bool ok(int x,int y){
  if(x<0||y<0||x+1>=n||y+1>=m)return false;
  REP(i,2)REP(j,2)if(fld[x+j][y+i]!=flg[j][i])return false;
  return true;
}
int rec(int x,int y){
  int res=0;
  for(int dx=-1;dx<=0;dx++){
    for(int dy=-1;dy<=0;dy++){
      if(ok(x+dx,y+dy))res++;
    }
  }
  return res;
}
int main(){
  cin>>m>>n;
  REP(i,m)REP(j,n)cin>>fld[j][i];
  REP(i,2)REP(j,2)cin>>flg[j][i];
  int pre=0;
  REP(i,m-1)REP(j,n-1){
    bool f=true;
    REP(x,2)REP(y,2){
      if(fld[j+x][i+y]!=flg[x][y])f=false;
    }
    if(f)pre++;
  }
  int ans=0;
  REP(i,m)REP(j,n){
    int cnt=rec(j,i);
    char t=fld[j][i];
    REP(k,3){
      fld[j][i]=tmp[k];
      ans=max(ans,pre-cnt+rec(j,i));
    }
    fld[j][i]=t;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 2192
#include<bits/stdc++.h>
#define ll long long
#define met(a) memset(a,0,sizeof(a))
#define inf 0x3f3f3f3f
//met(dp,0x7F);
using namespace std;
const int mod=1e9+7;
const int N=1e6+10;
int s[300010];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    met(s);
    int i,j,m,n;
    cin>>m>>n;
    int cnt=n,ans;
    if(m%2)
    {
        for(i=1; i<=n; i++)
            s[i]=(m+1)/2;
        for(i=1; i<=n/2; i++)
        {
            if(s[cnt]==1)
                cnt--;
            else
            {
                s[cnt]--;
                for(j=cnt+1; j<=n; j++)
                    s[j]=m;
                cnt=n;
            }
        }
        for(i=1; i<=cnt; i++)
            cout<<s[i]<<' ';
    }
    else
    {
        cout<<m/2;
        for(i=2; i<=n; i++)
            cout<<' '<<m;
        cout<<endl;

    }
    return 0;
}


Measured memory_bytes: 3456
#include <stdio.h>
int partition(int,int);
int A[100000];

int main(){
    int n,i,j,result;

    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d",&A[i]);
    }
    result = partition(0,n-1);

    for(i=0;i<n;i++){
        if(i==result){
            printf("[%d]",A[i]);
            if(i==n-1) printf("\n");
            else printf(" "); 
            continue;
        }
        if(i<n-1) printf("%d ",A[i]);
        else printf("%d\n",A[i]);
    }
    return 0;
}

int partition(int p,int r){
    int x,i,j,tmp;

    x = A[r];
    i = p-1;
    for(j=p;j<r;j++){
        if(A[j]<=x){
            i = i+1;
            tmp = A[i];
            A[i] = A[j];
            A[j] = tmp;
        }
    }
        tmp = A[i+1];
        A[i+1] = A[r];
        A[r] = tmp;
    return i+1;
}


Measured memory_bytes: 2228
#include <bits/stdc++.h>
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) FOR(i, 0, n)
#define ll long long
using namespace std;

const ll P = 1000000007;
int gcd(int a, int b) { return b != 0 ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }

int main()
{
  cout << fixed << setprecision(10);
  int N;
  cin >> N;
  cout << N/3 << endl;
  return 0;
}


Measured memory_bytes: 256
def culc(a, plus):
    sum = 0
    ans = 0
    for i in range(len(a)):
        sum += a[i]
        if plus:
            if sum <= 0:
                ans += abs(sum) + 1
                sum = 1
        else:
            if sum >= 0:
                ans += abs(sum) + 1
                sum = -1
        plus = not(plus)
    return ans

n = int(input())
a = list(map(int, input().split()))

ans1 = culc(a, True)
ans2 = culc(a, False)

print(min(ans1, ans2))

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

//マクロ
//forループ関係
//引数は、(ループ内変数,動く範囲)か(ループ内変数,始めの数,終わりの数)、のどちらか
//Dがついてないものはループ変数は1ずつインクリメントされ、Dがついてるものはループ変数は1ずつデクリメントされる
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//xにはvectorなどのコンテナ
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x)) //最大値を求める
#define MIN(x) *min_element(ALL(x)) //最小値を求める
//定数
#define INF 1000000000000 //10^12:極めて大きい値,∞
#define MOD 1000000007 //10^9+7:合同式の法
#define MAXR 100000 //10^5:配列の最大のrange(素数列挙などで使用)
#define PI 3.14159265359 //πの値
//略記
#define PB push_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素

 
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
  string S;
  cin >> S;
  if (S == "AAA" || S == "BBB") cout << "No";
  else cout << "Yes";
}


Measured memory_bytes: 256