akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vll = vector<vl>;
using vb = vector<bool>;
using vs = vector<string>;
using msi = map<string, int>;
using mii = map<int, int>;
using psi = pair<string, int>;
using pii = pair<int, int>;
using vlai = valarray<int>;
#define rep(i,n) for(int i=0;i<n;i++)
#define range(i,s,n) for(int i=s;i<n;i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define fs first
#define sc second
#define mp make_pair
#define INF 1E9
#define LINF 1E18*5
#define EPS 1E-9
#define MOD 1000000007
#define PI 3.1415926535897932384

template<class S, class T>ostream& operator<<(ostream&os, pair<S, T>p) { os << "[" << p.first << ", " << p.second << "]"; return os; };
template<class S>auto&operator<<(ostream&os, vector<S>t) { bool a = 1; for (auto s : t) { os << (a ? "" : " ") << s; a = 0; } return os; }

//int dx[]={1,1,1,0,-1,-1,-1,0},dy[8]={1,0,-1,-1,-1,0,1,1,1};
//
constexpr ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }

class compare {
public:
	bool operator()(tuple<int, int> a, tuple<int, int> b) {
		return (get<1>(a) < get<1>(b));
	}

};

int main() {
	ll ans = 0;
	string s;
	cin >> s;
	int n = s.size();
	vll vv(4, vl(n+1));
	vv[0][0] = 1;
	range(i,1,n+1) {
		if (s[i-1] == '?') {
			rep(j, 4) vv[j][i] = vv[j][i - 1] * 3;
			rep(j, 3) vv[j+1][i] += vv[j][i - 1];
		}
		else {
			vv[0][i] = vv[0][i - 1];
			vv[1][i] = vv[1][i - 1];
			vv[2][i] = vv[2][i - 1];
			vv[3][i] = vv[3][i - 1];
			if (s[i-1] == 'A') vv[1][i] += vv[0][i - 1];
			if (s[i-1] == 'B') vv[2][i] += vv[1][i - 1];
			if (s[i-1] == 'C') vv[3][i] += vv[2][i - 1];
		}
		rep(j, 4) vv[j][i] %= MOD;
	}
	cout << vv[3][n] << endl;
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define PI 3.141592653589793
#define rep(i, n) for (int i = 0; i < (n); i++)
#define REP(i, a, n) for (int i = a; i < (n); i++)
#define rrep(i, n, k) for (int i = (n); i >= (k); i--);
#define all(x) (x).begin(), (x).end()
#define vi vector<int>
#define pi pair<int, int>
#define pl pair<ll, ll>
template<class T> istream &operator>>(istream&is,vector<T>&v){for(auto &elemnt:v)is>>elemnt;return is;}
template<class T,class U> istream &operator>>(istream&is,pair<T,U>&p){is>>p.first>>p.second;return is;}
template<class T>vector<T> make_vector(size_t a){return vector<T>(a);}
template<class T, class... Ts>auto make_vector(size_t a, Ts... ts){return vector<decltype(make_vector<T>(ts...))>(a, make_vector<T>(ts...));}
const int MOD = 1e9+ 7;
const int INF = numeric_limits<int>::max() - 1e8;
const ll INFLL = numeric_limits<ll>::max() - 1e17;

int main() {
    int N;
    cin >> N;
    map<int, int> count;
    for (int i = 0; i < N; i++) {
        int a;
        cin >> a;
        count[a]++;
    }
    vector<vector<vector<double>>> dp(305, vector<vector<double>>(305, vector<double>(305, 0)));
    function<double(int, int, int)> calc = [&](int i, int j, int k) {
        tuple<int, int, int> explore = make_tuple(i, j, k);
        if (dp[i][j][k] != 0) return dp[i][j][k];
        if (i == j && j == k && i == 0) return 0.0;
        double temp = 0;
        if (i > 0) temp += calc(i - 1, j, k) * i;
        if (j > 0) temp += calc(i + 1, j - 1, k) * j;
        if (k > 0) temp += calc(i, j + 1, k - 1) * k;
        temp += N;
        temp /=  (double)(i + j + k);
        dp[i][j][k] = temp;
        return temp;
    };
    cout << fixed << setprecision(10) << calc(count[1], count[2], count[3]) << endl;
}


Measured memory_bytes: 225664
#include <bits/stdc++.h>
#define REP(i,n) for (int i = 0; i <(n); ++i)
#define ALL(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using P = pair<int,int>;
static const double PI = acos(-1);


ll lcm(ll x, ll y){
  ll ans;
  ans = x /__gcd(x,y) * y;
  return ans;

}

int main(){
  ll a, b;
  ll c, d;
  cin >> a >> b >> c >> d;

  ll x, y, xy;
  x = b/c - (a-1)/c;
  y = b/d - (a-1)/d;
  ll e = lcm(c,d);
  xy = b/e - (a-1)/e;

  //cout << x << " " << y << " " << xy << endl;

  ll ans;
  ans = b - a + 1 - x - y + xy;

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 3588
n=int(input())
a=[int(j) for j in input().split()]
l=a[:2]
if a[0]<=a[1]:b=True
else:b=False
for i,j in zip(a,a[1:]):
    if i<j:
        if b:
            l[-1]=j
        else:
            l.append(j)
            b=True
    elif i>j:
        if b:
            l.append(j)
            b=False
        else:
            l[-1]=j
ans=1000
for i,j in zip(l,l[1:]):
    if i<j:
        ans=(ans//i)*j+ans%i
print(ans)

Measured memory_bytes: 9212
#include<stdio.h>
int main(void){
int A,B;
scanf("%d %d",&A,&B);
if(A%3==0){
printf("Possible");
}else if(B%3==0){
printf("Possible");
}else if((A+B)%3==0){
printf("Possible");
}else{
printf("Impossible");
}
return 0;
}

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

int main() {
  double R;
  cin >> R;
  cout << fixed << setprecision(9) << R * 2 * 3.1416 << endl;
}

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

int main(void){
    int x;
    int sum = 0;
    std::cin >> x;

    sum += 1000 * std::floor(x / 500);
    x = x - 500 * std::floor(x / 500);
    sum += 5 * std::floor(x / 5); 

    std::cout << sum << std::endl;
}

Measured memory_bytes: 256
from copy import copy
from collections import defaultdict
n, p = map(int, input().split())

s = input()
ans = 0
if p == 2 or p == 5:
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i + 1
else:
    dp = [0] * p
    dp[0] = 1
    tmp = 0
    for i in range(n)[::-1]:
        tmp = (int(s[i]) * pow(10, n - i - 1, p) + tmp) % p
        # tmp = (int(s[i]) * 10 ** (n - i - 1) + tmp) % p
        # print(tmp, int(s[i]) * 10 ** (n - i - 1))
        ans += dp[tmp]
        dp[tmp] += 1 
    # print(dp)

print(ans)

Measured memory_bytes: 41308
process.stdin.resume();
process.stdin.setEncoding('ascii');

var input_stdin = "";
var input_stdin_array = "";
var input_currentline = 0;

process.stdin.on('data', function (data) {
    input_stdin += data;
});

process.on('SIGINT', function(){
    input_stdin_array = input_stdin.split("\n");
    main();
    process.exit();
});

process.stdin.on('end', function () {
    input_stdin_array = input_stdin.split("\n");
    main();    
});

function readLine() {
    return input_stdin_array[input_currentline++];
}

/////////////// ignore above this line ////////////////////

function main() {
	var s = readLine();	
	
	
	for (var i=0; i + 1 < s.length; i++){
		if (s[i] == s[i+1]){
			console.log((i+1).toString() + " " + (i+2).toString());
			return;
		}
	}
	for (var i=0; i + 2 < s.length; i++){
		if (s[i] == s[i+2]){
			console.log((i+1).toString() + " " + (i+3).toString());
			return;
		}
	}
	
	console.log("-1 -1");
}

Measured memory_bytes: 7500
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<sstream>
#include<stack>
#include<string>
#include<unordered_set>
#include<vector>

#define ll long long
#define P pair<int,int>
#define FOR(i,N) for(int i=0;i<(int)N;i++)
#define FORIN(i,a,b) for(int i=a;i<(int)b;i++)
#define ALL(x) (x).begin(),(x).end()
#define LAST(x) (x)[(x).size()-1]
#define GI(name) int (name);scanf("%d",&(name))
#define GI2(name1,name2) int (name1),(name2);scanf("%d %d",&(name1),&(name2))
#define GI3(name1,name2,name3) int (name1),(name2),(name3);scanf("%d %d %d",&(name1),&(name2),&(name3))
#define GVI(name,size) vector<int> (name)(size);FOR(i,(size))scanf("%d",&(name)[i])
#define MOD 1000000007

using namespace std;

string to_hex(int x){
    stringstream ss;
    ss<<hex<<x;
    return ss.str();
}

inline int get_int(){
    int ret;
    scanf("%d",&ret);
    return ret;
}

inline vector<int> get_ints(int n){
    vector<int> ret(n);
    FOR(i,n){
        scanf("%d",&ret[i]);
    }
    return ret;
}

inline string get_str(){
    string ret;
    cin>>ret;
    return ret;
}

bool is_prime(int n){
    int s=sqrt(n)+1;
    for(int i=2;i<=s;++i){
        if(n%i==0){
            return 0;
        }
    }
    return 1;
}

vector<P> prime_division(int n){
    vector<P> ret;
    int s=sqrt(n)+1;
    int c=0;
    for(int i=2;i<=n;++i){
        if(n%i==0){
            c=0;
            do{
                ++c;
                n/=i;
            }while(n%i==0);
            ret.push_back(P(i,c));
        }
    }
    return ret;
}

struct UnionFind{
    vector<int> data;
    UnionFind(int size){
        data=vector<int>(size,-1);
    }
    bool union_set(int x,int y){
        x=root(x);
        y=root(y);
        if(x!=y){
            if(data[y]<data[x])swap(x,y);
            data[x]+=data[y];
            data[y]=x;
        }
        return x!=y;
    }
    bool find(int x,int y){
        return root(x)==root(y);
    }
    int root(int x){
        return data[x]<0?x:data[x]=root(data[x]);
    }
    int size(int x){
        return -data[root(x)];
    }
};

string to_string(string s){
    return s;
}

template<class T>
string to_string(vector<T> v){
    string ret="{";
    FOR(i,v.size()-1){
        ret+=to_string(v[i])+",";
    }
    if(v.size()>0){
        ret+=to_string(LAST(v));
    }
    ret+="}";
    return ret;
}

void debug_print(){
    cerr<<endl;
}

template<class Head,class... Tail>
void debug_print(Head head,Tail... tail){
    cerr<<to_string(head)<<" ";
    debug_print(tail...);
}

template<class... T>
void debug(T... args){
    cerr<<"["<<__LINE__<<"]: ";
    debug_print(args...);
}

void print(){
    cout<<endl;
}

template<class Head,class... Tail>
void print(Head head,Tail... tail){
    cout<<to_string(head);
    print(tail...);
}

int main(){
    string s=get_str();
    string ans="";
    FOR(i,s.size()){
        if(s[i]=='B'){
            if(ans.size()>0){
                ans.erase(ans.end()-1);
            }
        }else{
            ans+=s[i];
        }
    }
    print(ans);
    return 0;
}

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

using namespace std;

int y,m,d,tmp,now;

int main(){
	scanf("%d/%d/%d",&y,&m,&d);
	now = 2019*365+4*30+30;
	tmp = y*365+m*30+d;
	if(tmp>now) printf("TBD\n");
	else printf("Heisei\n");
	return 0;
}

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

int main(){
    int n;
    cin >> n;
    bool Y = false;
    for(int i=0; i<n; i++){
        string s;
        cin >> s;
        if(s == "Y") Y = true;
    }
    if(Y) cout << "Four" << endl;
    else cout << "Three" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FI first
#define SE second
#define VE vector<int>
#define PB push_back
#define PA pair<int,int>
#define MA make_pair
#define ll long long
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ROF(i,a,b) for(int i=b-1;i>=a;i--)
#define YES(i) cout<<(i?"YES":"NO")<<endl
#define Yes(i) cout<<(i?"Yes":"No")<<endl
#define POS(i) cout<<(i?"POSSIBLE":"IMPOSSIBLE")<<endl
#define Pos(i) cout<<(i?"Possible":"Impossible")<<endl
#define co(i) cout<<i<<endl
#define fcout cout<<fixed<<setprecision(10)
using namespace std;

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

const int MAX_N=100010;
int par[MAX_N];
int rnk[MAX_N];

void init(int n){
    FOR(i,0,n){
        par[i]=i;
        rnk[i]=0;
    }
}

int find(int x){
    if(par[x]==x) return x;
    else return par[x]=find(par[x]);
}

void unite(int x,int y){
    x=find(x);
    y=find(y);
    if(x==y) return;
    if(rnk[x]<rnk[y]){
        par[x]=y;
    }else{
        par[y]=x;
        if(rnk[x]==rnk[y]) rnk[x]++;
    }
}

bool same(int x,int y){
    return find(x)==find(y);
}


int n,m;
int k[100010];
int used[100010]={};

int main(){
	cin>>n>>m;
	init(100010);
	FOR(i,0,n){
		cin>>k[i];
		int l1; cin>>l1;
		used[l1]=1;
		FOR(j,0,k[i]-1){
			int l2; cin>>l2;
			unite(l1,l2);
			used[l2]=1;
		}
	}
	bool ans=true;
	int ne=INF;
	FOR(i,0,100010){
		if(used[i]){
			if(ne==INF) ne=find(i);
			else{
				if(ne!=find(i)) ans=false;
			}
		}
	}
	YES(ans);
}

Measured memory_bytes: 1664
#include<iostream>

using namespace std;

int main()
{
	int n;
	int a[20000], b[20000];
	int a_score;
	int b_score;
	int score_stock[20000][2];
	int i, j;
	for(j = 0;;j++){
		a_score = 0;
		b_score = 0;
		cin >> n;		//J[hÌ
		if(n == 0){
			break;
		}
		
		for(i = 0;i < n; i++){
			cin >> a[i];
			cin >> b[i];
		}
		
		for(; i > -1; i--){
			if(a[i] > b[i]){
				a_score += a[i] + b[i];
			}
			else if(a[i] < b[i]){
				b_score += a[i] + b[i];
			}
			else{
				a_score += a[i];
				b_score += b[i];
			}
		}
		score_stock[j][0] = a_score;
		score_stock[j][1] = b_score;
	}
	for(i = 0; i < j; i++){
		cout << score_stock[i][0] << " "<<score_stock[i][1] << endl;
	}
}

Measured memory_bytes: 0
#include <stdio.h>

int main(void) {
    int a, b;
    int d, r;
    double f;

    scanf("%d %d", &a, &b);
    d = a / b;
    r = a % b;
    f = (double)a / (double)b;
    printf("%d %d %.05f\n", d, r, f);
    
    return 0;
}


Measured memory_bytes: 2100
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <numeric>
#include <string>

using namespace std;

int main(void){
    char s;
    cin>>s;
    
    char ans;
    if(s=='A'){
        ans='T';
    }else if(s=='T'){
        ans='A';
    }else if(s=='G'){
        ans='C';
    }else if(s='C'){
        ans='G';
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n,m;
long long a[1200][3],f[1200],res,cur;
int main(){
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=0;j<3;j++)
			cin>>a[i][j];
	}
	for(int mask=0;mask<8;mask++){
		int t;
		cur=0;
		for(int i=1;i<=n;i++){
			f[i]=0;
			t=mask;
			for(int j=0;j<3;j++){
				if(t%2==0)
					f[i]+=a[i][j];
				else
					f[i]-=a[i][j];
				t/=2;
			}
		}
		sort(f+1,f+n+1);
		reverse(f+1,f+n+1);
		for(int i=1;i<=m;i++){
			cur+=f[i];
		}
		res=max(res,cur);
	}
	cout<<res<<endl;
	return 0;
}


Measured memory_bytes: 256
import math
N, M = map(int,input().split())
a = [int(input()) for i in range(M)]
b = [-1]+ a+ [N+1]
fib = [0,1]
for i in range(10**5):
    fib.append((fib[-1]+fib[-2])%1000000007)
ans = 1
for i in range(len(b)-1):
    ans= (ans*fib[b[i+1]-b[i]-1])%1000000007
print(ans)

Measured memory_bytes: 11672
n = int(input())
r = [(0, 0, 0)]
for _ in range(n):
    t, x, y = [int(x) for x in input().split()]
    r.append((t, x, y))
for i in range(1, len(r)):
    l = abs(r[i][1] - r[i - 1][1]) + abs(r[i][2] - r[i - 1][2])
    t = r[i][0] - r[i - 1][0]
    if l > t or (l - t) % 2 == 1:
        print("No")
        exit()
print("Yes")

Measured memory_bytes: 17320
S = int(input())
a = S // 100
b = S % 100

if (a > 12 or a == 0) and 0 < b <= 12:
  print("YYMM")
elif 0 < a <= 12 and (b > 12 or b == 0):
  print("MMYY")
elif 0 < a <= 12 and 0 < b <= 12:
  print("AMBIGUOUS")
else:
  print("NA")

Measured memory_bytes: 3060
#include <cstdio>
#include <algorithm>
#define MAX 200000

typedef struct _p
{
    char name[100];
    int time;
} Process;

Process P[MAX];
int n, q, head, tail;

Process dequeue()
{
    Process p = P[head];
    head = (head + 1) % MAX;
    return p;
}

void enqueue(Process p)
{
    P[tail] = p;
    tail = (tail + 1) % MAX;
}

int main()
{
    int elaps = 0; // 時刻
    int t; // 処理時間
    Process u;
    scanf("%d %d", &n, &q);
    for (int i = 0; i < n; i++)
    {
        scanf("%s", P[i].name);
        scanf("%d", &P[i].time);
    }
    head = 0;
    tail = n;

    while (head != tail)
    {
        u = dequeue();
        t = std::min(u.time, q);
        elaps += t;
        u.time -= t;

        if (u.time > 0)
        {
            enqueue(u);
        }
        else
        {
            printf("%s %d\n", u.name, elaps);
        }
    }

    return 0;
}



Measured memory_bytes: 21912
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sn = new Scanner(System.in);
        String input = sn.next();
        String[] str=new String[2];
        str[0]= input.charAt(0)+""+input.charAt(1)+"";
        str[1]= input.charAt(2)+""+input.charAt(3)+"";
        int[] deta = new int[2];
        deta[0]= Integer.parseInt(str[0]);
        deta[1]= Integer.parseInt(str[1]);
        int count=0;
        boolean flag=false;
        for(int i=0;i<2;i++){
            if (deta[i]>0&&deta[i]<=12) {
                count++;
                if (i==0){
                    flag=true;
                }
            }
        }
        if(count==0){
            System.out.println("NA");
        }else if (count==2){
            System.out.println("AMBIGUOUS");
        }else if(count==1){
            if(flag){
                System.out.println("MMYY");
            }else{
                System.out.println("YYMM");
            }
        }


    }
}


Measured memory_bytes: 21716
#include"bits/stdc++.h"
#include<cassert>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
const int mod = 1000000007;
const int inf = 1ll << 61;
typedef pair<int, int> P;
typedef pair<int, P>PP;
struct edge {
	int to, cost;
};
vector<int>G[200006];
int s[200006];

void dfs(int now, int par) {
	for (int e : G[now]) {
		if (e == par)continue;
		s[e] += s[now];
		dfs(e, now);
	}
}

signed main() {
	int n, q; cin >> n >> q;
	rep(i, n - 1) {
		int a, b; cin >> a >> b;
		G[a - 1].push_back(b - 1);
		G[b - 1].push_back(a - 1);
	}

	rep(i, q) {
		int p, x; cin >> p >> x;
		s[p - 1] += x;
	}
	dfs(0, -1);
	rep(i, n)cout << s[i] << endl;
}

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

struct UnionFind
{
	vector<int> uni;

	UnionFind(int n) : uni(n, -1) {}
	int root(int a)
	{
		if (uni[a] < 0) return a;
		return uni[a] = root(uni[a]);
	}

	bool connect(int a, int b)
	{
		a = root(a);
		b = root(b);
		if (a == b) return false;
		if (uni[a] > uni[b])
		{
			a ^= b;
			b ^= a;
			a ^= b;
		}
		uni[a] = uni[a] + uni[b];
		uni[b] = a;
		return true;
	}

	bool isConnect(int a, int b)
	{
		return root(a) == root(b);
	}

	int size(int a)
	{
		return -uni[root(a)];
	}
};

signed main(void)
{
	int n;
	int m;
	int mx;

	cin >> n >> m;
	UnionFind uf(n);
	rep(i, m)
	{
		int a, b;
		cin >> a >> b;
		a--; b--;
		if (!uf.isConnect(a, b)) uf.connect(a, b);
	}
	mx = 0;
	rep(i, n)
		mx = max(mx, uf.size(i));
	cout << mx << endl;
	return 0;
}


Measured memory_bytes: 3976
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        try (Scanner in = new Scanner(System.in)) {
            int A = in.nextInt();
            int B = in.nextInt();

            for (int i = 0;; i++) {
                if (i * (A - 1) + 1 >= B) {
                    System.out.println(i);
                    return;
                }
            }
        }
    }
}


Measured memory_bytes: 27072
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
using ll = long long;

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

    int x[3], k;
    for (int h = 0; h < 3; h++) {
        cin >> x[h];
    }
    cin >> k;

    vector<ll> a[3];
    for (int h = 0; h < 3; h++) {
        a[h] = vector<ll>(x[h]);
        for (int i = 0; i < x[h]; i++) {
            cin >> a[h][i];
        }
        sort(a[h].begin(), a[h].end(), greater<>());
    }

    vector<ll> r;
    for (int i0 = 0; i0 < x[0]; i0++) {
        if (i0 + 1 > k) break;
        for (int i1 = 0; i1 < x[1]; i1++) {
            if ((i0 + 1) * (i1 + 1) > k) break;
            for (int i2 = 0; i2 < x[2]; i2++) {
                if ((i0 + 1) * (i1 + 1) * (i2 + 1) > k) break;
                r.push_back(a[0][i0] + a[1][i1] + a[2][i2]);
            }
        }
    }
    partial_sort(r.begin(), r.begin() + k, r.end(), greater<>());

    for (int i = 0; i < k; i++) {
        cout << r[i] << '\n';
    }
    cout << flush;

    return 0;
}

Measured memory_bytes: 1404
#[allow(unused_imports)]
use std::cmp::Reverse;

#[allow(unused_imports)]
use proconio::{fastout, input, marker::Chars};

#[allow(unused_imports)]
use itertools::Itertools;

#[fastout]
pub fn main() {
    input! {
        n: usize,
        w: usize,
        items: [(usize, usize); n],
    }

    const MAX_VALUE: usize = 100001;

    let mut dp = vec![vec![std::usize::MAX; MAX_VALUE]; n + 1];
    dp[0][0] = 0;
    for i in 0..n {
        for j in 0..MAX_VALUE {
            if j < items[i].1 || dp[i][j - items[i].1] == std::usize::MAX {
                dp[i + 1][j] = dp[i + 1][j].min(dp[i][j]);
            } else {
                dp[i + 1][j] = dp[i + 1][j].min(dp[i][j].min(dp[i][j - items[i].1] + items[i].0));
            }
        }
    }
    println!(
        "{}",
        dp[n]
            .iter()
            .enumerate()
            .filter(|(_, e)| **e <= w)
            .map(|(j, _)| j)
            .max()
            .unwrap()
    );
}


Measured memory_bytes: 81260
/*
    Author  :   jignesh1604
    College :   SVNIT
*/

#include<bits/stdc++.h>
using namespace std;

void solve() {
    string s , d;
    cin >> s >> d;
    long long int n = s.size() , m = d.size() , i , j;
    vector<vector<long long int>> dp(n+1 , vector<long long int> (m+1 , 0));
    for(i = 1 ; i <= n ; i++) {
        for(j = 1 ; j <= m ; j++) {
            if(s[i-1] == d[j-1]) {
                dp[i][j] = 1+dp[i-1][j-1];
            }
            else {
                dp[i][j] = max(dp[i-1][j] , dp[i][j-1]);
            }
        }
    }
    i = n;
    j = m;
    string fin = "";
    while(i > 0 && j > 0) {
        if(s[i-1] == d[j-1]) {
            fin += s[i-1];
            i--;
            j--;
        }
        else {
            if(dp[i-1][j] > dp[i][j-1]) {
                i--;
            }
            else {
                j--;
            }
        }
    }
    reverse(fin.begin() , fin.end());
    cout << fin << "\n";
}

int main() {
    long long int tc = 1;
    // cin >> tc;
    while(tc-- > 0) {
        solve();
    }
}

Measured memory_bytes: 73648
import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String b =sc.nextLine();
		if(b.equals("A")) {
			System.out.println("T");
		}else if(b.equals("T")) {
			System.out.println("A");
		}else if(b.equals("G")) {
			System.out.println("C");
		}else if(b.equals("C")) {
			System.out.println("G");
		}
		sc.close();
	}

}

Measured memory_bytes: 21204
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main(void){
    string s;cin>>s;
    string p, pp, q, qq;
    p=s.substr(0, int(s.size()-1)/2);
    pp=p;
    q=s.substr(int(s.size()+1)/2);
    qq=q;
    string ss=s;
    reverse(s.begin(), s.end());
    reverse(p.begin(), p.end());
    reverse(q.begin(), q.end());
    if(s==ss&&pp==p&&q==qq)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

Measured memory_bytes: 256
import math
 
X = int(input())
x=int(math.sqrt(X))


for i in range(X,200001):
    c=0
    for j in range(2,x+1):
        if i%j != 0:
            continue
        else:
            c=1
            break
    if c==0:
        print(i)
        break


Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define PI 3.141592653589793238
int main()
{
    // #ifndef ONLINE_JUDGE
    // freopen("F:/cpp/input.txt", "r", stdin);
    // freopen("F:/cpp/output.txt", "w", stdout);
    // #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    char ch;
    cin >> ch;
    if (ch <= 'Z')
    cout << "A";
    else
    cout << "a";
    return 0;
}

Measured memory_bytes: 3644
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
#include <utility>
using namespace std;

#define rep2(x,from,to) for(int x=(from);(x)<(to);(x)++)
#define rep(x,to) rep2(x,0,to)
int n, q;
queue<pair<string, int> > qu;
int main() {
	cin >> n >>	q;
	rep(i,n) {
		string s;
		int t;
		cin >> s >> t;
		qu.push(make_pair(s, t));	
	}
	int time = 0;
	while(!qu.empty()) {
		pair<string, int> p = qu.front();
		qu.pop();
		if(p.second > q) {
			p.second -= q;
			time += q;
			qu.push(p);
		} else {
			time += p.second;
			cout << p.first << " " << time << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 4404
#include<bits/stdc++.h>
#define EPS 1e-10
#define equals(a,b) (fabs((a)-(b)) < EPS)
#define rep(i,n) for(int i=0;i<n;++i)
typedef long long ll;
using namespace std;

static const int COUNTER_CLOCKWISE = 1;
static const int CLOCKWISE = -1;
static const int ONLINE_BACK = 2;
static const int ONLINE_FRONT = -2;
static const int ON_SEGMENT = 0;

// 点
struct Point {
    double x,y;
    Point(){}
    Point(double x, double y) : x(x),y(y){}
    Point operator+(Point p) {return Point(x+p.x, y+p.y);}
    Point operator-(Point p) {return Point(x-p.x, y-p.y);}
    Point operator*(double k){return Point(x*k,y*k);}
    Point operator/(double k){return Point(x/k,y/k);}
    double norm(){return x*x+y*y;}
    double abs(){sqrt(norm());}
    bool operator == (const Point &p) const {return equals(x,p.x)&&equals(y,p.y);}
};

typedef Point P;
typedef vector<Point> Polygon;

double cross(Point a, Point b) {return a.x*b.y-a.y*b.x;}

double area(Polygon s){
    double res=0;
    for(int i=0;i<(int)s.size();i++){
        res+=cross(s[i],s[(i+1)%s.size()])/2.0;
    }
    return res;
}

// 内積
double dot(Point a, Point b) {return a.x*b.x + a.y*b.y;}

// 2直線の直行判定
bool is_orthogonal(Point a1, Point a2, Point b1, Point b2) {
    return equals(dot(a1-a2, b1-b2), 0.0);
}
// 2直線の平行判定
bool is_parallel(Point a1, Point a2, Point b1, Point b2) {
    return equals(cross(a1-a2, b1-b2), 0.0);
}
// 点cが直線ab上にあるかないか
bool is_point_on_INF_line(Point a, Point b, Point c) {
    return equals(cross(b-a,c-a), 0.0);
}
// 点cが線分ab上にあるかないか
bool is_point_on_LIMITED_line(Point a, Point b, Point c) {
    return (Point(a-c).abs()+Point(c-b).abs() < Point(a-b).abs() + EPS);
}
// 直線と点の距離
double distance_l_p(Point a, Point b, Point c) {return abs(cross(b-a, c-a)) / (b-a).abs();}

// 点a,bを端点とする線分と点cとの距離
double distance_ls_p(Point a, Point b, Point c) {
    if (dot(b-a, c-a) < EPS) return (c-a).abs();
    if (dot(a-b, c-b) < EPS) return (c-b).abs();
    return abs(cross(b-a, c-a)) / (b-a).abs();
}

// 点が線分のどちら側にあるかを計算
int ccw(Point p0,Point p1,Point p2) {
    P a = p1-p0;
    P b = p2-p0;
    if(cross(a,b) > EPS) return COUNTER_CLOCKWISE;
    if(cross(a,b) < -EPS) return CLOCKWISE;
    if(dot(a,b) < -EPS) return ONLINE_BACK;
    if(a.norm()<b.norm()) return ONLINE_FRONT;
    return ON_SEGMENT;
}

bool isConvex(Polygon p){
    bool f=1;
    int n=p.size();
    for(int i=0;i<n;i++){
        int t=ccw(p[(i+n-1)%n],p[i],p[(i+1)%n]);
        f&=t!=CLOCKWISE;
    }
    return f;
}

int main() {
    int n;cin>>n;
    Polygon pl;
    rep(i,n) {
        double x,y; cin>>x>>y;
        pl.push_back(Point(x,y));
    }
    if (isConvex(pl)) cout << 1 << endl;
    else cout << 0 << endl;
}


Measured memory_bytes: 3232
import java.util.*;

public class Main implements Runnable {

    private static int MOD = 1_000_000_007;

    public static void main(String[] args) {
        // Run with 32MB stack
        Thread thread = new Thread(null, new Main(), "", 32 * 1024 * 1024);
        thread.start();
    }

    @Override
    public void run() {
        final Scanner scanner = new Scanner(System.in);
        solve(scanner);
    }

    static void solve(Scanner scanner) {
        int N = Integer.parseInt(scanner.next());
        int K = Integer.parseInt(scanner.next());

        int[][] list = new int[N][2];
        for (int i = 0; i <N; i++) {
            list[i][0] = Integer.parseInt(scanner.next());
            list[i][1] = Integer.parseInt(scanner.next());
        }

        Arrays.sort(list, Comparator.comparing(x -> -x[1]));

        Queue<Integer> removable = new PriorityQueue<>();
        Set<Integer> added = new HashSet<>();
        long oishi = 0;
        long kind = 0;

        for (int i = 0; i < K; i++) {
            oishi += list[i][1];
            if (added.add(list[i][0])) {
                kind++;
            } else {
                removable.add(list[i][1]);
            }
        }

        long max = oishi + kind * kind;
        for (int i = K; i < N; i++) {
            if (removable.isEmpty()) {
                break;
            }
            if (added.add(list[i][0])) {
                oishi -= removable.poll();
                oishi += list[i][1];
                kind++;
                max = Math.max(max, oishi + kind * kind);
            }
        }

        System.out.println(max);
    }
}



Measured memory_bytes: 68832
#include<stdio.h>
#include<string>
#include<utility>
#include<iostream>
#include<queue>
#include<math.h>
#include<algorithm>
#include<vector>
#include<map>
#include<stack>
#include<bitset>

using namespace std;
typedef long long ll;
#define REP(i,n) for(int i=0;i<(int)(n);i++)

int main(){
    int a,b,c;
    cin >> a >> b >> c;
    bool flag = true;
    if(a==b && a!=c)flag=false;
    if(a==c && a!=b)flag = false;
    if(b==c&&a!=b)flag = false;
    if(flag)cout<<"No"<<endl;
    else cout <<"Yes"<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
template<class T> inline void fix(T &x) {if(x >= mod | x <= -mod) {x %= mod;} if(x < 0) {x += mod;}}

ll fpow(ll x, ll p) {
    if(p == 0) {return 1;}
    ll ans = fpow(x, p / 2);
    ans = (ans * ans) % mod;
    if(p & 1) {
        return (ans * x) % mod;
    } else {
        return ans;
    }
}

const int MAX_N = 2e5 + 10;
vector<int> g[MAX_N];
ll sz[MAX_N], ans[MAX_N], p[MAX_N], invp[MAX_N];
ll n;
void dfs1(int x, int par) {
    sz[x] = ans[x] = 1;
    for(auto it : g[x]) {
        if(it == par) {continue;}
        dfs1(it, x);
        sz[x] += sz[it];
        ans[x] = (((ans[x] * ans[it]) % mod) * invp[sz[it]]) % mod;
    }
    ans[x] = (ans[x] * p[sz[x] - 1]) % mod;
}

ll ret[MAX_N];

void dfs2(int x, int par, ll come) {
    ret[x] = (((invp[sz[x] - 1] * ans[x]) % mod) * p[n - 1]) % mod;
    ret[x] = (((ret[x] * come) % mod) * invp[n - sz[x]]) % mod;
    for(auto it : g[x]) {
        if(it == par) {continue;}
        ll toCome = ((((ret[x] * invp[n - 1]) % mod) * ((fpow(ans[it], mod - 2) * p[n - 1 - sz[it]]) % mod) % mod) * p[sz[it]]) % mod;
        dfs2(it, x, toCome % mod);
    }
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    p[0] = invp[0] = 1;
    for(int i = 1; i < MAX_N; i ++) {
        p[i] = (p[i - 1] * i) % mod;
        invp[i] = fpow(p[i], mod - 2);
    }
    cin >> n;
    for(int i = 0; i < n - 1; i ++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs1(1, 0);
    dfs2(1, 0, 1);
    for(int i = 1; i <= n; i ++) {
        cout << ret[i] << endl;
    }
    return 0;
}




Measured memory_bytes: 21748
#include <bits/stdc++.h>
using namespace std;
int main () {
    int n;
    cin >> n;
    int a[100010];
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    int k = 1;
    for (int i = 1; i <= n; i++) {
        k = a[k];
        if (k == 2) {
            cout << i << endl;
            return 0;
        }
    }
    puts("-1");
}

Measured memory_bytes: 640
main = do
    l <- getLine
    let (w:h:x:y:r:[]) = map read $ words l :: [Float]
    let isContain = (contain x w r) && (contain y h r)
    putStrLn $ if isContain then "Yes" else "No"


contain :: Float -> Float -> Float -> Bool
contain x w r
    | x < (w / 2) =  x >= r
    | x >= (w / 2) = (w - x) >= r



Measured memory_bytes: 3756
X, Y, A, B, C = map(int, input().split())
P = sorted(list(map(int, input().split())), reverse=True)
Q = sorted(list(map(int, input().split())), reverse=True)
R = sorted(list(map(int, input().split())), reverse=True)


P = P[:X]
Q = Q[:Y]
print(sum(sorted(P + Q + R, reverse=True)[:X+Y]))

Measured memory_bytes: 23200
#include<bits/stdc++.h>
#include<string>
#include<cmath>

using namespace std;

#define ll long long int
#define ld long double
#define loop(i, n) for (int i = 0; i < n; i++)
#define loops(i, s, n) for (int i = s; i < n; i++)
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
#define deb(x) cout<< #x << '=' << x <<endl
#define MOD 1000000007

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

    int n;
    ld d;
    cin>>n>>d;
    ld x[n],y[n];
    for(int i = 0; i < n; i++){
        cin>>x[i]>>y[i];
    }
    ll ans = 0;
    for(int i = 0; i < n; i++){
        ld dist = sqrt(x[i]*x[i] + y[i]*y[i]);
        if(dist <= d){
            ans++;
        }
    }
    cout<<ans;
}

Measured memory_bytes: 10072
#include <cstdio>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <list>
#include <map>
#include <set>
#include <stack>
#include <bitset>
#include <climits>
#include <utility>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define REP(i,n) for(int (i)=0;i<(int)(n);++(i))
#define REPIT(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
#define PB push_back
#define FT first
#define SD second
#define ZERO(x) memset(x,0,sizeof(x))
#define NEG(x) memset(x,-1,sizeof(x))
#define RI(x) scanf("%d",&(x))
#define RII(x,y) scanf("%d%d",&(x),&(y))
#define RIII(x,y,z) scanf("%d%d%d",&(x),&(y),&(z))
#define OIII(x,y,z) printf("%d %d %d\n",(x),(y),(z))
#define OII(x,y) printf("%d %d\n",(x),(y))
#define OI(x) printf("%d\n",(x))
#define OL(x) cout<<(x)<<endl
#define OLL(x,y) cout<<(x)<<" "<<(y)<<endl
#define OLLL(x,y,z) cout<<(x)<<" "<<(y)<<" "<<(z)<<endl
#define RS(s) scanf("%s",(s))
#define MP(x,y) make_pair((x),(y))
#define SZ(x) ((int)(x).size())
#define FIN(f) freopen(f,"r",stdin)
#define FOUT(f) freopen(f,"w",stdout)
typedef long long LL;
using namespace std;
typedef pair<int,int> PII;
const int MOD = 1e9+7;
const int maxn = 222222;
int n,m;
int r[maxn], ind[maxn];
int main(int argc, char const *argv[])
{
    RII(n,m);
    r[1] = 1;
    for(int i=1;i<=n;++i)ind[i] = 1;
    REP(i,m) {
        int x,y;
        RII(x,y);
        ind[y]++;
        ind[x]--;
        if(r[x]) {
            r[y] = 1;
            if(ind[x]==0)r[x] = 0;
        }
    }
    int ans = 0;
    for(int i=1;i<=n;++i)if(r[i]>0)ans++;
    OI(ans);
    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
using namespace std;
int main(){
	int n,k;
	unsigned int no=1;
	cin >> n >> k;
	for(int i=0;i<n;i++){
		if(k + no > (no << 1))
			no <<= 1;
		else
			no += k;
	}
	cout << no << endl;
}

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

int main() {
  int N; cin >> N;
  bool flag = false;
  for(int i = 1; i < 10; ++i){
    if(N%i == 0 && N/i < 10) flag = true;
  }
  
  if(flag) cout << "Yes" << endl;
  else cout << "No" << endl;
}

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

int main() {
  int side_num = 0;
  int paint_white_num = 0;
  // 入力
  cin >> side_num >> paint_white_num;
  
  // 出力
  cout << side_num * side_num - paint_white_num << endl;
}

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

int div_sum(int n) {
  int sum = 0;
  while ( n > 0) {
    sum += n % 10;
    n /= 10; 
  }
  return sum;
}


int main () {
int n, a, b;
cin >> n >> a >> b;

  int total = 0;
  for (int i = 1; i <= n; i++) {
    int sum = div_sum(i);
    if(a <= sum && sum <= b) total += i; 
  }

  cout << total << endl;

}

Measured memory_bytes: 256
#include <cstdio>

using namespace std;

char s[300][301];
int ans[300][300];

int main() {
    int h, w, k, c = 0, i, j, l;
    
    scanf("%d %d %d", &h, &w, &k);
    
    for (i = 0; i < h; i++) scanf("%s", s[i]);
    
    for (i = 0; i < h; i++) {
        for (j = 0; j < w; j++) {
            if (s[i][j] == '.') continue;
            
            c++;
            
            for (l = j; l >= 0; l--) {
                if (ans[i][l] > 0) break;
                
                ans[i][l] = c;
            }
        }
    }
    
    for (i = 0; i < h; i++) {
        if (ans[i][0] == 0) continue;
        
        for (j = 1; j < w; j++) {
            if (ans[i][j] == 0) ans[i][j] = ans[i][j - 1];
        }
    }
    
    for (i = h - 2; i >= 0; i--) {
        if (ans[i][0] > 0) continue;
        
        for (j = 0; j < w; j++) {
            if (ans[i + 1][j] > 0) ans[i][j] = ans[i + 1][j];
        }
    }
    
    for (i = 1; i < h; i++) {
        if (ans[i][0] > 0) continue;
        
        for (j = 0; j < w; j++) {
            if (ans[i - 1][j] > 0) ans[i][j] = ans[i - 1][j];
        }
    }
    
    for (i = 0; i < h; i++) {
        for (j = 0; j < w; j++) {
            if (j > 0) putchar(' ');
            printf("%d", ans[i][j]);
        }
        puts("");
    }
    
    return 0;
}


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

void hoge(){
	int i,j;
	for(i=1;i<=9;i++){
	 for(j=1;j<=9;j++){
	  cout<<i<<"x"<<j<<"="<<i*j<<endl;
	 }
	}
}

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

Measured memory_bytes: 1116
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using namespace std;

template<class T>
constexpr T INF = ::numeric_limits<T>::max() / 32 * 15 + 208;

int main() {
    double t, x;
    cin >> t >> x;
    cout << setprecision(15) << t/x << "\n";
    return 0;
}


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

using ll = long long;
#define ALL(c) (c).begin(), (c).end()
const int MOD = 1000000007;


int main() {
    int a, p;
    cin >> a >> p;
    cout << (a * 3 + p) / 2 << endl;

}


Measured memory_bytes: 256
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		int n = scan.nextInt();
		int m = scan.nextInt();
		int dn[] = new int[n];
		int ans = 0;
		
		for(int i=0;i<n;i++) {
			dn[i] = -1;
		}
		for(int i=0;i<m;i++) {
			int s = scan.nextInt();
			int c = scan.nextInt();
			if((dn[s-1] != -1 && dn[s-1] != c) || (s==1 && n!=1 && c==0)) {
				System.out.println(-1);
				System.exit(0);
			}else {
				dn[s-1] = c;				
			}
		}
		
		for(int i=0;i<n;i++) {
			if(dn[i] == -1 && (i==0 && n!=1)) {
				dn[i] = 1;
			}else if(dn[i] == -1) {
				dn[i] = 0;
			}
			
			ans += dn[i] * Math.pow(10,n-1-i);
		} 
		
		System.out.println(ans);
		
	}
	
}




Measured memory_bytes: 23764
import java.util.*;
class Main {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int a = s.nextInt();
        int b = s.nextInt();
        int c = s.nextInt();
        System.out.println(c >= a && c <= b ? "Yes" : "No");
    }
}

Measured memory_bytes: 22996
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n)     for(int i = 0; i < (int)(n); i++)
#define rep2(i, m, n) for(int i = m; i <= (int)(n); i++)
#define Graph vector<vector<int>>
#define MOD 1000000007 
#define PMAX 1000000 

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


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

  vector<int> A(N);

  int ans = 0;
  rep(i,N) {
    cin >> A[i];
    ans += A[i];
  }

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


Measured memory_bytes: 256
#import sys
#import numpy as np
#from collections import defaultdict
#import math
#from collections import deque

#input = sys.stdin.readline
#import decimal

def main():
    a,b,c = map(int,input().split())

    if a ==b:
        if a!=c:
            print("Yes")
            exit()
        else:
            print("No")
            exit()
    if a ==c:
        if a!=b:
            print("Yes")
            exit()
        else:
            print("No")
            exit()
    if b ==c:
        if a!=c:
            print("Yes")
            exit()
        else:
            print("No")
            exit()

    print("No")
if __name__ == "__main__":
    main()

Measured memory_bytes: 9116
#include <bits/stdc++.h> //C++の標準ライブラリを一行で一括でインクルードする
#include <math.h> //数学関数と数学定数を利用する
#define rep(i,n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;
template<class T> void chmax(T &a,T b) { if (a<b) a=b;}
template<class T> void chmin(T &a,T b) { if (a>b) a=b;}
int gcd(int a, int b){//ユークリッドの互除法
  if (a < b) gcd(b,a); //aの方がbよりでかいのが前提
  if (b == 0) return a; //aをbで割り切れたらreturn
  else gcd(b, a % b);
}

int main(){
  ll n,l; cin >> n >> l;
  vector<ll> a(n);
  rep(i,n) cin >> a[i];
  
  int pos = 0; bool check = false;
  rep(i,n-1){
    if(a[i]+a[i+1] >= l){
      check = true;
      pos = i+1;
      break;
    }
  }
  
  if(check){
    cout << "Possible" << endl;
    for(int i = 1; i<pos;i++){
      cout << i << endl;
    }
    for(int i = n-1; i>pos;i--){
      cout << i << endl;
    }
    cout << pos << endl;
  }else{
    cout << "Impossible" << endl;
  }
  
  return 0;
}

Measured memory_bytes: 1664
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<functional>
#include<cmath>
#include<map>
using namespace std;
int n, m, a, b; vector<int>x[100009]; int used[100009]; bool OK = false;
void dfs(int pos, int dep) {
	if (used[pos] != -1) {
		if (dep != used[pos])OK = true;
		return;
	}
	used[pos] = dep;
	for (int i = 0; i < x[pos].size(); i++)dfs(x[pos][i], dep ^ 1);
}
int main() {
	cin >> n >> m; for (int i = 1; i <= n; i++)used[i] = -1;
	for (int i = 0; i < m; i++) { cin >> a >> b; x[a].push_back(b); x[b].push_back(a); }
	dfs(1, 0);
	int V1 = 0, V2 = 0;
	for (int i = 1; i <= n; i++) { if (used[i] == 0)V1++; else V2++; }
	if (OK == false)cout << 1LL * V1*V2 - m << endl;
	else cout << (1LL * n*(n - 1) / 2LL) - (1LL * m) << endl;
	return 0;
}

Measured memory_bytes: 6912
#include<bits/stdc++.h>
using namespace std;
signed main(void)
{
	 int k;
	map<int,pair<int,int> >mp;
	for(int  i = 0;i<3;i++)
		for(int  j = 0;j<3;j++)
			{
				cin>>k;
               mp[k].first = i;
               mp[k].second = j;
 			}
		int n;
		cin>>n;

	bool mat[3][3];
	memset(mat,false,sizeof mat); 
	for(int  i = 0;i<n;i++)
	{
         cin>>k;
         if(mp.find(k)!=mp.end())
         {
         	  mat[(mp[k].first)][(mp[k].second)]=true;
         }
	}

	bool found = false;

	for(int  i = 0;i<3;i++)
	{
		if((mat[i][0] && mat[i][1] && mat[i][2]) || (mat[0][i] && mat[1][i] && mat[2][i]))
		 found = true;
	}

	if(mat[0][0] && mat[1][1] && mat[2][2])
	  found = true;
	if(mat[2][0] && mat[1][1] && mat[0][2])
	  found = true;

	if(found)
	 cout<<"Yes"<<endl;
	else
	cout<<"No"<<endl;     	
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stdio.h>
#include <queue>
#include <stack>
#include <climits>
#include <map>
#include <set>

using namespace std;

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

const ll mod = 1000000007;
const int inf = 1e9;
const long long INF = 1LL << 60;


int main()
{
    double a,b,x;
    cin >> a >> b >> x;
    double l,ans;
    if(a*a*b < 2 * x){
        int d = a * a * b - x;
        l = (d * 2.0) / (a * a);
        ans = atan(l/a) / M_PI * 180;
        
    }else{
        l = (x * 2.0) / (a * b);
        ans = atan(b/l) / M_PI * 180;
    }
    printf("%.10lf",ans);
}

Measured memory_bytes: 256
import std.algorithm, std.container, std.conv, std.math, std.range, std.typecons, std.stdio, std.string;

auto rdsp(){return readln.splitter;}
void pick(R,T)(ref R r,ref T t){t=r.front.to!T;r.popFront;}
void pickV(R,T...)(ref R r,ref T t){foreach(ref v;t)pick(r,v);}
void readV(T...)(ref T t){auto r=rdsp;foreach(ref v;t)pick(r,v);}

void main()
{
  int q; readV(q);

  auto a1 = Array!int().heapify!"a<b", s1 = 0L;
  auto a2 = Array!int().heapify!"a>b", s2 = 0L;
  auto bs = 0L, u = 0, c = 0;

  foreach (_; 0..q) {
    auto rd = rdsp;
    int typ; pick(rd, typ);
    switch (typ) {
    case 1:
      int a, b; pickV(rd, a, b);
      bs += b;

      if (u%2 == 0) {
        if (a1.empty || a2.empty) {
          c = a;
        } else if (a1.front > a) {
          a1.insert(a); s1 += a;
          c = a1.front; a1.removeFront(); s1 -= c;
        } else if (a2.front < a) {
          a2.insert(a); s2 += a;
          c = a2.front; a2.removeFront(); s2 -= c;
        } else {
          c = a;
        }
      } else {
        a1.insert(c); s1 += c;
        a1.insert(a); s1 += a;
        auto t = a1.front; a1.removeFront(); s1 -= t;
        a2.insert(t); s2 += t;
      }

      ++u;
      break;
    case 2:
      if (u%2 == 0)
        writeln(a1.front, " ", s2-s1+bs);
      else
        writeln(c, " ", s2-s1+bs);
      break;
    default:
      assert(0);
    }
  }
}


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

int main() {
    int n, m, i, a;
    cin >> n >> m;
    vector<int> ans(n, 0);
    for (i = 0; i < m*2; i++){
        cin >> a;
        ans.at(a-1) += 1;
    }

    for (i = 0; i < n; i++){
        cout << ans.at(i) << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;
const long long INF = 1LL << 60;

int main() {
  int N; cin>>N;
  int usagi[N+1];
  for(int i=1; i<=N; i++) cin>>usagi[i];
  int count=0;
  for(int i=1; i<=N; i++){
    if(usagi[usagi[i]]==i) count++;
  }	
  cout<<count/2<<endl;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
int n,k,ass,a[51];
bool mmp(int a,int b)
{
    return a>b;
}
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    sort(a+1,a+n+1,mmp);
    for(int i=1;i<=k;i++)   
        ass+=a[i];
    cout<<ass<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define PI 3.141592653589793238462643383279502884L
#define lli long long int
#define d double
using namespace std;
 
int main() {
	FIO;
	lli n,w;
	cin>>n>>w;
	vector<pair<lli,lli>> vec(n+1);
	for(lli i=1;i<=n;i++){
		lli x,y;
		cin>>x>>y;
		vec[i].first=x;
		vec[i].second=y;
	}
	vector<vector<lli>> dp(n+1,vector<lli>(w+1,0));
	for(lli i=1;i<=n;i++){
		for(lli j=1;j<=w;j++){
			dp[i][j]=max(dp[i-1][j],j-vec[i].first>=0?vec[i].second+dp[i-1][j-vec[i].first]:0);
		}
	}
	cout<<dp[n][w]<<endl;
	return 0;
}

Measured memory_bytes: 80256
#include "bits/stdc++.h"

using namespace std;

#define sp(x) cout<<setprecision(x);
#define all(a) (a).begin(), (a).end()
#define inf 10000000
#define linf INT64_MAX*0.99
#define print(s) cout<<(s)<<endl
#define lint long long
#define FOR(i,a,b) for(lint i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define yes "Yes"
#define no "No"
#define divs 1000000007
#define dive 1000000009

typedef pair<int, int> P;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    lint n; cin>>n;
    vector<lint> p(n);
    REP(i,n) cin>>p[i];
    lint low;
    lint ans = 1;
    REP(i,n){
        if(i==0) low = p[0];
        else{
            if(low>p[i]){
                ans++;
                low = p[i];
            }
        }
    }
    print(ans);
    return 0;
}

Measured memory_bytes: 1792
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;

int gcd(int a, int b){
  if(b==0) return a;
  else gcd(b, a%b);
}
  
int main(){
  int N; ll X;
  cin >> N >> X;
  ll a[N+1];
  rep(i, N){
    cin >> a[i];
  }
  a[N] = X;
  sort(a, a+N+1);
  ll b[N];
  rep(i, N){
    b[i]=a[i+1]-a[i];
  }
  
  ll tmp, ans=0;
  rep(i, N){
    tmp = gcd(b[0], b[i]);
    ans = gcd(tmp, ans);
  }
  cout << ans << endl;
  
}

Measured memory_bytes: 1792