akhauriyash/Code-Regression huggingface dataset:
import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        FastScanner sc = new FastScanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        ArrayList<Integer> li = new ArrayList<>();
        char[] s = sc.next().toCharArray();
        boolean is0 = s[0] == '0' ? true : false;
        int cnt0 = is0 ? 1 : 0;
        li.add(0);
        if(is0){
            li.add(0);
        }
        int now = 1;
        for(int i = 1; i < n; i++){
            if(is0 && s[i] == '0' || !is0 && s[i] == '1'){
                now++;
            }else if(!is0 && s[i] == '0'){
                is0 = true;
                li.add(now);
                now = 1;
                cnt0++;
            }else{
                is0 = false;
                li.add(now);
                now = 1;
            }
        }
        li.add(now);
        if(s[n-1] == '0'){
            li.add(0);
        }
        int[] arr = new int[li.size()];
        for(int i = 0; i < li.size(); i++){
            if(i != 0){
                arr[i] = li.get(i) + arr[i-1];
            }else{
                arr[i] = li.get(i);
            }
        }
        if(cnt0 <= k){
            System.out.println(n);
            return;
        }else{
            int ans = 0;
            for(int i = 0; i < li.size()/2-k; i++){
                ans = Math.max(ans,arr[i*2+k*2+1]-arr[i*2]);
            }
            System.out.println(ans);
        }
    }
}

class FastScanner {
    private BufferedReader reader = null;
    private StringTokenizer tokenizer = null;
    public FastScanner(InputStream in) {
        reader = new BufferedReader(new InputStreamReader(in));
        tokenizer = null;
    }

    public String next() {
        if (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }

    public String nextLine() {
        if (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                return reader.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken("\n");
    }

    public long nextLong() {
        return Long.parseLong(next());
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

    public double nextDouble() {
         return Double.parseDouble(next());
    }

    public int[] nextIntArray(int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++)
            a[i] = nextInt();
        return a;
    }

    public long[] nextLongArray(int n) {
        long[] a = new long[n];
        for (int i = 0; i < n; i++)
            a[i] = nextLong();
        return a;
    } 
}


Measured memory_bytes: 28628
using System;
using System.Linq;
using System.Collections.Generic;
class Program
{
    static void Main()
    {
        var num = int.Parse(Console.ReadLine());
        var input = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToList();
        var count = 0;

        while (true)
        {
            if (input.All(x => x % 2 == 0))
            {
                input = input.Select(x => x = x / 2).ToList();
                count++;
            }
            else
            {
                break;
            }
        }

        Console.WriteLine(count);
    }
}

Measured memory_bytes: 13396
def modinv(a,m):
    return pow(a,m-2,m)

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

P = 10**9+7

nCa = 1

for i in range(1,a+1):
    nCa = nCa*(n+1-i)*modinv(i,P)%P
nCb = nCa
for j in range(a+1,b+1):
    nCb = nCb*(n+1-j)*modinv(j,P)%P

ans = (pow(2,n,P) -1 - nCa - nCb + 2*P)%P
print(ans)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int n,p;
    while (cin>>n>>p) {
        if (n==0&p==0) {
            break;
        } else {
            std::deque<int> deq(n,0);
            int i=0;
            while (1) {
                if (p!=0) {
                    p-=1;
                    deq[i]++;
                    i++;
                    if (i>n-1) {
                        i=0;
                    }
                } else if (p==0) {
                    int flag=0;
                    for (int j=0;j<n;j++) {
                        if (i!=j&&deq[j]!=0) {
                            flag=1;
                            break;
                        }
                    }
                    if (flag==0) {
                        break;
                    } else {
                        p=deq[i];
                        deq[i]=0;
                        i++;
                        if (i>n-1) {
                            i=0;
                        }
                    }
                }
            }
            cout<<i<<endl;
        }
    }
}



Measured memory_bytes: 3076
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <string>
#include <iterator>
#include <cmath>
#include <deque>
#include <stack>
#include <functional>
#include <queue>

signed main()
{
    {
        if (fopen("input.txt", "r")) {
            freopen("input.txt", "r", stdin);
            freopen("output.txt", "w", stdout);
        }
        std::ios_base::sync_with_stdio(false);
        std::cin.tie(NULL);
        std::cout.tie(NULL);
    }

    std::string t;
    std::cin >> t;
    if (t[0] == '?')
        t[0] = 'D';
    for (int i = 1; i < t.size(); ++i)
        if (t[i] == '?')
            t[i] = 'D';
    std::cout << t;
    return 0;
}

Measured memory_bytes: 3784
n = int(input())
x = list(map(int, input().split()))
y = list(map(int, input().split()))
d = [abs(x[i] - y[i]) for i in range(n)]
for i in range(1,4):
    print('{0:f}'.format(sum(j ** i for j in d) ** (1 / i)))
print('{0:f}'.format(max(d)))


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

int main(int argc, char **argv)
{
	ll A, B; cin >> A >> B;
	if (A == B) std::cout << 0 << std::endl;
	else if ((A + B) % 2 == 0)
	{
		std::cout << (A+B)/2<< std::endl;
	}
	else
		std::cout << "IMPOSSIBLE" << std::endl;
}


Measured memory_bytes: 256
#pragma GCC optimize ("O3")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <stack>
#include <unordered_map>
#define lld long long int
#define dbg1(vari1) cerr<<#vari1<<" = "<<(vari1)<<endl;
#define dbg2(vari1,vari2) cerr<<#vari1<<" = "<<(vari1)<<" "<<#vari2<<" = "<<(vari2)<<endl;
#define dbg3(vari1,vari2,vari3) cerr<<#vari1<<" = "<<(vari1)<<" "<<#vari2<<" = "<<(vari2)<<" "<<#vari3<<" = "<<(vari3)<<endl;
using namespace std;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin >> n;
	int arr[n];
	for(int i=0;i<n;i++)
		cin >> arr[i];
	int ch=1;
	for(int i=0;i<n;i++)
	{
		if(arr[i]==ch)
			ch++;
	}
	if(ch==n+1)
		cout << "0";
	else if(ch==1)
		cout << "-1";
	else
		cout << n-ch+1;
}

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

    using namespace std;
    int main(){
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
        string s;
        string t;
        cin>>s>>t;
        int n=s.size();
        int m=t.size();
        vector<vector<int>>a(n+1,vector<int>(m+1));
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(s[i-1]==t[j-1])
                    a[i][j]=a[i-1][j-1]+1;
                else
                    a[i][j]=max({a[i-1][j],a[i][j-1]});
            }
        }
//        for(int i=0;i<=n;i++){
//            for(int j=0;j<=m;j++)
//                cout<<a[i][j]<<" ";
//            cout<<"\n";
//        }
        string ans="";
        int x=n,y=m;
        while(y!=0 && x!=0){
            if(a[x-1][y]==a[x][y])
                --x;
            else if(a[x][y-1]==a[x][y])
                --y;
            else{
                ans=t[y-1]+ans;
                --y;
                --x;
            }
        }
        cout<<ans;
        return 0;
    }


Measured memory_bytes: 35584
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
//#include <bits/stdc++.h> 

using namespace std;
//ABC150E
int main(){
    int N;
    cin>>N;
    long int C[N];
    for (int i=0;i<N;i++) cin>>C[i];
    sort(C,C+N,greater<long int>());
    long int n=1,INF=1000000007;
    if (N==1){
        cout<<(2*C[0])%INF<<endl;
        return 0;
    }
    for (int i=0;i<N-2;i++){
        n=2*n;
        n=n%INF;
    }
    long long x=1,ans=0;
    for (int i=0;i<N;i++){
        x=(i+2)*n;
        x=x%INF;
        x=x*C[i];
        x=x%INF;
        ans+=x;
        ans=ans%INF;
    }
    ans=ans*n*4;
    ans=ans%INF;
    cout<<ans<<endl;
  
    return 0;
}

Measured memory_bytes: 5160
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>

static const int MOD = 998244353;
using ll = int64_t;
using namespace std;

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

template <class T, class U>
vector<T> make_v(U size, const T& init){ return vector<T>(static_cast<size_t>(size), init); }

template<class... Ts, class U>
auto make_v(U size, Ts... rest) { return vector<decltype(make_v(rest...))>(static_cast<size_t>(size), make_v(rest...)); }

template<class T> void chmin(T &a, const T &b){ a = (a < b ? a : b); }
template<class T> void chmax(T &a, const T &b){ a = (a > b ? a : b); }


int main() {
    ll n;
    cin >> n;
    vector<array<int, 2>> v(n);
    for (auto &&i : v) scanf("%d %d", &i[0], &i[1]);
    vector<ll> p2(n+1);
    p2[0] = 1;
    for (int i = 0; i < n; ++i) {
        p2[i+1] = p2[i]*2%MOD;
    }
    ll ans = (p2[n]+MOD-1-n-n*(n-1)/2) % MOD;
    auto checked = make_v(n, n, 0);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if(!checked[i][j]){
                vector<int> u;
                u.emplace_back(i); u.emplace_back(j);
                for (int k = 0; k < n; ++k) {
                    if(k != i && k != j){
                        if((v[k][0]-v[i][0])*(v[j][1]-v[i][1]) ==
                            (v[k][1]-v[i][1])*(v[j][0]-v[i][0])) u.emplace_back(k);
                    }
                }
                for (auto &&l : u) {
                    for (auto &&k : u) {
                        checked[l][k] = 1;
                    }
                }
                int w = static_cast<int>(u.size());
                if(w >= 3) (ans += (MOD- p2[w]+w+w*(w-1)/2 + 1)) %=  MOD;
            }
        }
    }
    cout << (ans%MOD+MOD)%MOD << "\n";
    return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <functional>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
using namespace std;
using llong = long long;

llong h, n;
llong a[100005];
llong sum = 0;

int main() {
    cin >> h >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        sum += a[i];
    }

    if (sum >= h) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}


Measured memory_bytes: 1024
#include <climits>
#include <iostream>
#include <iterator>
#include <queue>
#include <vector>
using namespace std;

int ans;

void mergeSort(vector<int>::iterator a, vector<int>::iterator b) {
	if (1 + a < b) {
		ans += b - a;
		mergeSort(a, next(a, (b - a) / 2));
		mergeSort(next(a, (b - a) / 2), b);
		queue<int> c, d;
		for (vector<int>::iterator i = a; i != next(a, (b - a) / 2); ++i) c.push(*i);
		c.push(INT_MAX);
		for (vector<int>::iterator i = next(a, (b - a) / 2); i != b; ++i) d.push(*i);
		d.push(INT_MAX);
		for (vector<int>::iterator i = a; i != b; ++i) {
			if (c.front() < d.front()) {
				*i = c.front();
				c.pop();
			}
			else {
				*i = d.front();
				d.pop();
			}
		}
	}
}

int main() {
	int n;
	cin >> n;
	vector<int> S(n);
	for (int& i : S) cin >> i;
	mergeSort(S.begin(), S.end());
	for (int i = 0; i < n - 1; ++i) cout << S[i] << ' ';
	cout << S.back() << endl << ans << endl;
}


Measured memory_bytes: 6920
#include<stdio.h>
int main(){
  char s[201]={0};
  int i,n,j,c,h=0;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    h=0;
    scanf("%s",s);
    if(s[0]=='>'){
      if(s[1]=='\''){
	c=0;
	for(j=2;s[j]=='=';j++)c++;
	if(s[j++]=='#'&&c!=0){
	  for(;s[j]=='=';j++)c--;
	  if(c==0&&s[j]=='~'&&s[j+1]==0)h=1;
	}
      }
      if(s[1]=='^'){
	h=2;
	for(j=2;s[j]=='Q';j+=2){
	  if(s[j+1]!='='){
	    h=0;
	    break;
	  }
	}
	if(!(s[j]=='~'&&s[j+1]=='~'&&s[j+2]==0&&j!=2))h=0;
      }
    }
    if(h==0)printf("NA\n");
    if(h==1)printf("A\n");
    if(h==2)printf("B\n");
  }
  return 0;
}

Measured memory_bytes: 584
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
using st=string;
using ch=char;
typedef pair<ll,ll> P;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<P> vP;
typedef vector<ch> vc;
typedef vector<vc> vvc;
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) FOR(i,0,n)
#define ROF(i,a,b) for(ll i=a;i>=b;i--)
#define per(i,a) ROF(i,a,0)
#define pb push_back
#define mp make_pair
const ll MOD=1000000007;
const ll MOD2=998244353;
const ld PI=acos(-1);
const ll INF=1e18;
st abc="abcdefghijklmnopqrstuvwxyz";
st ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
struct edge{ll to,cost;};

int main() {
    ll x,n;
    cin >> x >> n;
    vl p(n);
    vl cnt(101,0);
    rep(i,n){
        cin >> p[i];
        cnt[p[i]]++;
    }
    ll d=INF,ans;
    FOR(i,-1000,1001){
        if(abs(x-i)<d&&((0<=i&&i<=100&&cnt[i]==0)||i<0||i>100)){
            d=abs(x-i);
            ans=i;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
int n, m, x, y;
vvi ns;
vi dp;

int solve(int node){

    int &ret=dp[node];
    if(ret != -1) return ret;

    ret=0;
    int sz=ns[node].size();
    for(int i=0;i<sz;i++){
        ret=max(ret, 1+solve(ns[node][i]));
    }

    return ret;

}

int main(){
    scanf("%d %d",&n,&m);
    ns=vvi(n), dp=vi(n, -1);
    for(int i=0;i<m;i++) {
        scanf("%d %d",&x,&y);
        x--, y--;
        ns[x].push_back(y);
    }

    int mx=0;
    for(int i=0;i<n;i++){
        mx=max(solve(i), mx);
    }

    printf("%d", mx);



    return 0;
}


Measured memory_bytes: 8192
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG //これつけるとA[N]でもいいらしい
//for文のマクロ
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define big 1000000007
#define all(a) sort((a).begin(),(a).end()) //ソートのマクロ
#define Re(a) reverse((a).begin(),(a).end())
#define YN(a) if(a){cout<<"Yes"<<endl;}else cout<<"No"<<endl;//条件によってYes、Noを出力する

int main(){
    //愚直にやったら間に合う?
    string s;
    cin>>s;
    int n = s.length();
    int fb=1;
    int64_t q;
    cin>>q;
    rep(i,q){
        int t;
        cin>>t;
        if(t==1){
            fb *= -1;
        }
        else{
            int f;
            char c;
            cin>>f>>c;
            if(f==1){//先頭にciを追加
                if(fb==1){
                    s.insert(s.begin(),c);
                }
                else{
                    s.push_back(c);
                }
            }
            else{//f==2 => 末尾にcを追加    
                if(fb==1){
                    s.push_back(c);
                }
                else{
                    s.insert(s.begin(),c);
                }
            }
        }
    }
    if(fb==1){
        rep(i,s.length()){
            cout<<s[i];
        }
    }
    else{
        for(int i=s.length()-1;i>=0;i--){
            cout<<s[i];
        }
    }
    cout<<endl;
}

Measured memory_bytes: 900
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
#define MOD 1000000007
#define MOD2 998244353
#define INF MOD
#define LINF (1LL<<60)
#define EPS (1e-10)
typedef long long Int;
typedef pair<Int, Int> P;

Int cnt[66000];

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

    for (int x = 1; x <= 100; x++) {
        for (int y = 1; y <= 100; y++) {
            for (int z = 1; z <= 100; z++) {
                int p = x*x + y*y + z*z + x*y + y*z + z*x;
                cnt[p]++;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        cout << cnt[i] << endl;
    }
}

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

using ll = long long;
#define f first
#define s second

#ifndef LOCAL
	#define cerr if(0) cerr
#endif

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

	int div = (n / 1000) + (n % 1000 != 0);
	div *= 1000;

	cout << div - n << "\n";
}


Measured memory_bytes: 3688
#include<bits/stdc++.h>
using namespace std;
#define ll long long
string s;
ll ans,cnt[2200],num,t=1;
int main()
{
	cin>>s;
	cnt[0]=1;	
	for(int i=s.size()-1;i>=0;i--)
	{
		num=(num+(s[i]-'0')*t)%2019;
		ans+=cnt[num];
		cnt[num]++;
		t=t*10%2019;
	}
	cout<<ans;
return 0;
}


Measured memory_bytes: 3712
// g++ -std=c++11 -O2 -Wall -Wl,--stack=268435456

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

typedef vector< int >      vi;
typedef vector< vi >       vvi;
typedef pair<int, int>     pi;
typedef vector< pi >       vpi;

typedef long long          ll;
typedef vector<ll>         vl;
typedef vector< vl >      vvl;

const int LARGE_INT = 1000000007;
const ll LARGE_LONG = 1L << 62;

#define F first
#define S second
#define PB push_back
#define MP make_pair
#define REP(i,a,b) for (int i = (int)(a); i < (int)(b); i++)

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int  n;
    string s, t;
    cin >> n >> s >> t;
    REP(i, 0, n) {
        cout << s[i] << t[i];
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 256
a,b,m=map(int,input().split())
al=list(map(int,input().split()))
bl=list(map(int,input().split()))
max=min(al)+min(bl)
for i in range (m):
    cl=list(map(int,input().split()))
    if(al[cl[0]-1]+bl[cl[1]-1]-cl[2]<max):
        max=al[cl[0]-1]+bl[cl[1]-1]-cl[2]
print(max)



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

const ll INF = 1LL << 62;
const double PI = acos(-1);
const double eps = 1e-10;

int main() {
  ll n;
  cin >> n;
  vector<vector<int>> g(n);
  vector<pair<int, int>> vp;
  rep(i, n - 1) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    g[a].push_back(b);
    g[b].push_back(a);
    vp.emplace_back(a, b);
  }

  map<P, int> ans;
  vector<int> cs(n, 0);
  vector<bool> used(n, false);
  queue<int> q;
  used[0] = true;
  q.push(0);
  while (!q.empty()) {
    int v = q.front();
    q.pop();
    int c = 1;
    for (int u : g[v]) {
      if (used[u]) continue;
      if (c == cs[v]) c++;
      cs[u] = ans[P(u, v)] = ans[P(v, u)] = c++;
      used[u] = 1;
      q.emplace(u);
    }
  }

  int k = 0;
  rep(i, n - 1) k = max(k, (int)g[i].size());
  cout << k << endl;
  for (auto p : vp) cout << ans[p] << endl;
  return 0;
}


Measured memory_bytes: 22300
#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>

using namespace std;

#define FOR(i,k,n) for(int i=(k); i<(int)n; ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cout<<*i<<" "; cout<<endl; }

typedef long long ll;
const ll INF = 100000000000000LL;
const double EPS = 1e-8;
const int MOD = 1000000007;

int main(){
  int n, m;
  while(cin>>n>>m && n){
    static ll dp[150][10][77] = {};
    REP(i, 150)REP(j, 10)REP(k, 77) dp[i][j][k] = INF;
    int k[151], x[151][151], s[151][151];
    REP(i, n){
      cin>>k[i];
      REP(j, k[i]) cin>>x[i][j]>>s[i][j];
    }
    REP(i, k[0]) dp[0][i][0] = 0;
    REP(i, k[1]) dp[1][i][1] = 0;
    for(int i = 0; i < n - 1; i++){
      for(int j = 0; j < k[i]; j++){
        int from_x = x[i][j];
        for(int l = 0; l < k[i + 1]; l++){
          int to_x = x[i + 1][l];
          for(int use = 0; use <= m; use++){
            dp[i + 1][l][use] = min(dp[i + 1][l][use], dp[i][j][use] + (s[i][j] + s[i + 1][l]) * abs(from_x - to_x));
          }
        }
        if(i + 2 < n){
          for(int l = 0; l < k[i + 2]; l++){
            int to_x = x[i + 2][l];
            for(int use = 0; use < m; use++){
              dp[i + 2][l][use + 1] = min(dp[i + 2][l][use + 1], dp[i][j][use] + (s[i][j] + s[i + 2][l]) * abs(from_x - to_x));
            }
          }
        }
      }
    }
    ll ans = INF;
    REP(i, k[n - 1])REP(j, m + 1) ans = min(ans, dp[n-1][i][j]);
    REP(i, k[n - 2])REP(j, m ) ans = min(ans, dp[n-2][i][j]);
    cout<<ans<<endl;
  }

  return 0;
}

Measured memory_bytes: 2236
import java.util.Scanner;
public class Main{

    int data,x;



    public void input(){
	Scanner scan = new Scanner(System.in);
	x = 1;
        while(true){
	    data = scan.nextInt();
	    if ( data == 0 ) break;
	    output();
	    x = x + 1;
	}
    }
    public void output(){
	System.out.println("Case "+x+":"+" "+data);
    }
    



    public static void main(String[] args){
	Main  p = new Main();
	p.input();
	//	p.output();
    }
}
 

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

int main()
{
  long x, a, b;
  cin >> x;
  cin >> a;
  cin >> b;
  long d = b - a;
  if( d <= 0 ) {
    cout << "delicious" << endl;
  } else if ( d <= x  ) {
    cout << "safe" << endl;
  } else {
    cout << "dangerous" << endl;
  }

  return 0;
}

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

// コンテスト中のみ
#define int long long


#define ll long long
#define rep(i,n) for(int i = 0; i < (n); i++)
int MOD = 1000000007;
const int inf = 1001001001;
const ll INF = 1LL << 60;

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, k; cin >> n >> k;
	vector<int>a(n); rep(i, n)cin >> a[i];
	int l = 0, r = 1e10;
	while (r - l > 1) {
		int mid = (l + r) / 2;
		int cnt = 0;
		rep(i, n) {
			cnt += (a[i] + mid - 1) / mid - 1;
		}
		if (cnt <= k) {
			r = mid;
		}
		else {
			l = mid;
		}
	}
	cout << r << endl;
	return 0;
}

Measured memory_bytes: 4748
#include<bits/stdc++.h>
using namespace std;
int n;
int main(){
	cin >> n;
	int x = 0, y = n - 1;
	string a, b;
	cout << x << endl;
	cin >> a;
	if( a == "Vacant")	
		return 0;
	cout << y << endl;
	cin >> b;
	if( b == "Vacant")
		return 0;
	int m = (x + y)/2;
	cout << m << endl;
	string c;
	cin >> c;
	if( c == "Vacant")
		return 0;
	if( c == a && (abs(x - m) - 1) % 2 == 0)
		y = m, b = c;
	else if( c == b &&  (abs(x - m) - 1) % 2 == 0)
		x = m , a = c;
	else if( c != a && (abs(x - m) - 1) % 2 == 1)
		y = m, b = c;
	else
		x = m, a = c;
	while( true ){
		m = (x + y)/2;
		cout << m << endl;
		cin >> c;
		if( c == "Vacant")
			return 0;
		if( c == a && (abs(x - m) - 1) % 2 == 0)
			y = m, b = c;
		else if( c == b &&  (abs(x - m) - 1) % 2 == 0)
			x = m , a = c;
		else if( c != a && (abs(x - m) - 1) % 2 == 1)
			y = m, b = c;
		else
			x = m, a = c;
	}
    return 0;
}

Measured memory_bytes: 852
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int k;
    int w=7;
    int ans=-1;
    cin>>k;
    for(int i=1;i<=k;i++){
        w=(w%k)*10+7;
        if(w==7){
            ans=i;
          	break;
        }
    }
    cout<<ans;
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
#define pb push_back
#define ff first
#define ss second
#define assign(x,val) memset(x,val,sizeof(x))
#define all(x) (x).begin(), (x).end()
#define for0(i,n) for(ll i=0;i<n;++i)
#define for1(i,n) for(ll i=1;i<=n;++i)
#define ford(i,n) for(ll i=n;i>=1;--i)
#define forg(i,a,b) for(ll i=a;i<b;++i)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpi;
typedef pair<ll, ll> pll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pll> vpl;
long long mod = 1000000007;
const long double PI = (long double)(3.1415926535897932384626433832795);


void solve(){
  string s;cin>>s;
  int x = s.length();
  int cnt = 0;
  int i = 0, j = x-1;
  while(i<j){
    if(s[i]!=s[j]) cnt++;
    ++i;--j;
  }
  cout<<cnt<<endl;
}

int main(){
	ll t = 1;
	//cin>>t;
	for0(i, t){
		solve();
	}
	return 0;
}


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

#define ll long long
#define mod 1000000007
#define pb push_back
#define pi pair<int,int>
#define vi vector<int>
#define vpi vector< pi > 
#define IOS ios_base::sync_with_stdio(false),cin.tie(NULL)
const int N=500003;

int main()
{
  double r;
  cin>>r;

  printf("%0.2lf",2*acos(-1)*r);
	
	return 0;
}

Measured memory_bytes: 3768
#include <bits/stdc++.h>
using namespace std;
 
#define fast { ios :: sync_with_stdio(false); cin.tie(0); cout.tie(0); }
#define pb push_back
#define ll long long
 
#define vi vector<int>
#define vl vector<long>
#define vll vector<long long>
 
#define infi INT_MAX
#define infl LONG_LONG_MAX
#define f(i,a,b) for(ll i=a;i<b;i++)
#define fi(i,a,b) for(ll i=(b-1);i>=a;i--)
#define F first
#define S second
#define G(a,b) get<a>(b)
#define MP make_pair
#define MT make_tuple
#define pll pair<ll,ll> 
#define endl "\n"
#define ALL(v) v.begin(),v.end()


const ll N=1e5+5;
list<ll>adj[N];
vll tps;
bool visited[N];

void dfs(ll v)
{
  visited[v]=1;
  for(auto i:adj[v])
  {
    if(!visited[i]) dfs(i);
  }
  tps.pb(v);
}

void func()
{
  ll n,m;
  cin>>n>>m;
  ll u,v;
  f(i,0,m)
  {
    cin>>u>>v;
    adj[u].pb(v);
  }
  f(i,1,n+1) if(!visited[i]) dfs(i);

  ll dp[n+1]={},mx=-1;
  for(auto i:tps)
  {
    for(auto j:adj[i])
    {
      dp[i]=max(dp[i],dp[j]+1);
    }
    mx=max(mx,dp[i]);
  }
  cout<<mx<<endl;
}

int main() 
{
    fast
    //freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
    
    ll ntc=1;
    //cin>>ntc;
 
    while(ntc)
    {
      func();
      ntc--;
    }
 
    return 0;
}

Measured memory_bytes: 8312
#include <bits/stdc++.h>
#define maxn 200005
int arr[maxn],n,seq[maxn],rank[maxn],ref[maxn];

int cmp(int a,int b){return arr[a]<arr[b];}

int check(int x){
//	printf("checking:%d\n",x);
	int mid=(n/2)+1;
	for (int i=1;i<=n;++i) {
		seq[i]=(ref[i]>x);
		//printf("%d ",seq[i]);
	}//printf("\n");
	if (seq[mid]==seq[mid-1]||seq[mid]==seq[mid+1]) return seq[mid];
	for (int i=1;i<n/2;++i)
		if (seq[mid-i]==seq[mid-i-1]||seq[mid+i]==seq[mid+i+1]) return seq[mid-i];
	return seq[1];
}

int main(){
//	freopen("triangle.in","r",stdin);
//	freopen("triangle.out","w",stdout);
	scanf("%d",&n);n=n*2-1;
	for (int i=1;i<=n;++i){
		scanf("%d",&arr[i]);
		rank[i]=i;
	}if (n==1) {printf("%d ",arr[1]);return 0;}
	std::sort(rank+1,rank+n+1,cmp);
	for (int i=1;i<=n;++i) ref[rank[i]]=i;
//	for (int i=1;i<=n;++i) printf("%d ",ref[i]); printf("\n");
	int l=1,r=n,ans=1;
	while (l<r){
		int mid=(l+r)>>1;
		if (check(mid)) l=mid+1;
		else {r=mid;ans=mid;}
	}printf("%d",arr[rank[ans]]);
	return 0;
}



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

const string YES = "Yes";
const string NO = "No";

void solve(long long A, long long B, long long C, long long D){
    while(true){
            C -= B;
            if(C <= 0){
                break;
            }
            A -= D;
            if(A <= 0){
                break;
            }
    }
    if(C <= 0){
        cout << YES << endl;
    }else{
        cout << NO << endl;
    }
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long A;
    scanf("%lld",&A);
    long long B;
    scanf("%lld",&B);
    long long C;
    scanf("%lld",&C);
    long long D;
    scanf("%lld",&D);
    solve(A, B, C, D);
    return 0;
}


Measured memory_bytes: 3768
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using P = pair<int,int>;
template <class T> void chmin(T &a, const T &b) noexcept { if (b < a) a = b; }
template <class T> void chmax(T &a, const T &b) noexcept { if (a < b) a = b; }
void debug_out() { cout << "\n"; }
template <class T, class... Args>
void debug_out(const T &x, const Args &... args) { cout << x << " "; debug_out(args...);}
#ifdef _DEBUG
  #define debug(...) debug_out(__VA_ARGS__)
#else
  #define debug(...) 
#endif

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(0);
  ll a; 
  long double b;
  cin >> a >> b;
  long double ans = a*b;
  cout << floor(ans) << endl;
  return 0;
}

Measured memory_bytes: 3808
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<sstream>
#include<unordered_map>
#include<unordered_set>
#include<vector>
using uint = unsigned int;
using ll = long long;
enum : int { M = (int)1e9 + 7 };
enum : ll { MLL = (ll)1e18L + 9 };
using namespace std;
#ifdef LOCAL
#include"rprint2.hpp"
#include"debug_deque.hpp"
#define vector DebugDeque
#else
#define FUNC(name) template <ostream& out = cout, class... T> void name(T&&...){ }
FUNC(prints) FUNC(printe) FUNC(printw) FUNC(printew) FUNC(printb) FUNC(printd) FUNC(printde);
#endif

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s; cin >> s;
    cout << (s[0] == s[1] && s[1] == s[2] || s[1] == s[2] && s[2] == s[3] ? "Yes" : "No") << '\n';
}


Measured memory_bytes: 256
def time_to_int(t):
    hh, mm, ss = map(int, t.split(':'))
    return hh*3600 + mm*60 + ss

from itertools import accumulate
def solve(n):
    res = [0]*(24*3600+1)
    for _ in range(n):
        s, t = map(time_to_int, input().split())
        res[s] += 1
        res[t] -= 1
    
    ress = accumulate(res)
    print(max(ress))

while True:
    n = int(input())
    if n == 0:
        break
    solve(n)



Measured memory_bytes: 6324
import sys
sys.setrecursionlimit(200000000)
n,q = map(int, input().split())
graph1 = [[] for _ in range(n+1)]
graph2 = [[] for _ in range(n+1)]
ans=[0]*(n+1)
reached=[0]*(n+1)
def main():
  for i in range(n-1):
    a,b = map(int, input().split())
    graph1[a].append(b)
    graph2[b].append(a)

  for i in range(q):
    p,x = map(int, input().split())
    ans[p] += x
  dfs(1) 
  print(' '.join([str(i) for i in ans[1:]]))

def dfs(i):
  if reached[i] == 1:
    return
  reached[i] = 1
  for g in graph1[i], graph2[i]:
    for j in g:
      if reached[j] == 1:
        continue
      ans[j] += ans[i]
      dfs(j)

if __name__ == '__main__':
  main()

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

int main(void) {
	char s[100005];
	int k;
	
	fgets(s,sizeof(s), stdin);
	scanf("%d", &k);
	int kariK = k;
	char tmp;
	int a;
	
	for(int i = 0; i < k; i++){
		a = s[i] - 'a';
		if(a + kariK >= 26 && a > 0){
			s[i] = 'a';
			kariK = a + kariK - 26;
			if(kariK == 0){
				break;
			}
		}
		
		if(i  >= strlen(s) - 2){
			s[i] += kariK % 26;
				if(s[i] - 'z' > 0){
					s[i] = s[i] -  'z';
				}
			break;
		}
	}
	
	printf("%s",s);
	
	return 0;
}

Measured memory_bytes: 384
n, m, k = map(int, input().split())
MOD = 998244353

def nck(n, k):
    numer, denom = 1, 1
    for i in range(k):
        numer *= n - i
        denom *= k - i
    return numer * pow(denom, MOD-2, MOD) % MOD

ans = 0
combination = 1
ans += m * pow(m-1, n-1, MOD) % MOD
for i in range(1, k+1):
    combination *= (n-i) * pow(i, MOD-2, MOD)
    combination %= MOD
    ans += combination * m * pow(m-1, n-1-i, MOD) % MOD
    ans %= MOD

print(ans)
    

Measured memory_bytes: 68252
#include<stdio.h>
#include<algorithm>
using namespace std;

int main() {
  long long x, i, j;
  scanf("%lld", &x);
  j = 0;
  for(i=0; i<=x; i++) {
    j = j + i;
    if(j >= x) {
      break;
    }
  }
  printf("%lld\n", i);
  return 0;
}

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

#define PI 3.14159265359

using ll = long long;
using VL = vector<ll>;
using VVL = vector<vector<ll>>;
using P = pair<ll, ll>;

// chmin, chmax関数
template<typename T, typename U, typename Comp=less<>>
bool chmax(T& xmax, const U& x, Comp comp={}) {
    if(comp(xmax, x)) {
        xmax = x;
        return true;
    }
    return false;
}
template<typename T, typename U, typename Comp=less<>>
bool chmin(T& xmin, const U& x, Comp comp={}) {
    if(comp(x, xmin)) {
        xmin = x;
        return true;
    }
    return false;
}

// Yes-Noを出力する問題で楽をする
void Ans(bool f){
    if(f) cout << "Yes" << endl;
    else cout << "No" << endl;
}

//---------------------------

int main(){
    double a,b; ll h,m;
    cin >> a >> b >> h >> m;
    double theta = 30*h - 5.5*m;
    double c = a/b + b/a - 2*cos(theta*PI/180.0);
    c = sqrt(c*a*b);
    cout << setprecision(12) << c << endl;
    return 0;
}

Measured memory_bytes: 4152
#include <stdio.h>

int main(void){
	int a = 0 , b = 0 , c = 0 , keta = 0;
	
	while(scanf("%d%d" ,&a ,&b) != EOF){
		c = a + b;
		while(c > 0){
			keta++;
			c = c / 10;
		}
		printf ("%d\n" ,keta);
		a = 0 ; b = 0 ; c = 0 ; keta = 0;
	}
	
	return (0);
}

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

#define rep(i,a,b) for (int i=a;i<=b;i++)

typedef long long ll;
typedef vector<vector<int>> vvi;
typedef vector<int> vi;

int find(vi& parent, int i)  
{  
    if (parent[i] == i)
        return i;
    parent[i] = find(parent, parent[i]);
    return parent[i];  
}  
  
void Union(vi& parent, int x, int y)  
{  
    int xset = find(parent, x);  
    int yset = find(parent, y);  
    if(xset != yset) 
    {  
        parent[xset] = yset;  
    }  
}  

int main() {
    int N, M;
    int x,y ;
    unordered_map<int,int> counter;
    cin >> N >> M;
    vi parent(N);
    rep(i,0,N-1) {
        parent[i] = i;
    }
    rep(i,0,M-1){
        cin >> x >> y;
        x--; y--;
        Union(parent, x,y);
    }  
    int j, res{0};
    rep(i,0,N-1) {
        j = find(parent, i);
        counter[j]++;
        res = max(res, counter[j]);
    }
    cout << res;
    return 0;
}


Measured memory_bytes: 12116
D = {}
N = int(input())
for _ in range(N):
    a = input()
    if a in D:
        D[a] += 1
    else:
        D[a] = 1
M = int(input())
for _ in range(M):
    a = input()
    if a in D:
        D[a] -= 1
    else:
        D[a] = -1
ma = 0
for a in D:
    ma = max(ma, D[a])
print(ma)

Measured memory_bytes: 38384
#include <bits/stdc++.h>
#define sz(x) (int)(x).size()
#define For(i, a, b) for (int i = int(a); i < int(b); i++)
#define Dor(i, a, b) for (int i = int(b) - 1; i >= int(a); i--)
#define Foz(i, a) For(i, 0, a)
#define Doz(i, a) Dor(i, 0, a)
#define Trav(e, v) for (auto& e : v)
#define pb push_back
#define mp make_pair
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vii = vector<ii>;
template <typename T> bool ckmin (T& a, T b) { return (b < a) ? a = b, 1 : 0; }
template <typename T> bool ckmax (T& a, T b) { return (b > a) ? a = b, 1 : 0; }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#ifdef XVENOM
	#define errp(...) fprintf(stderr, __VA_ARGS__)
	#define dbg(...) errp("[%s]: ", #__VA_ARGS__), dbg_str(__VA_ARGS__)
#else
	#define errp(...)
	#define dbg(...)
#endif
template <typename U, typename V> string to_string (pair<U, V>);
string to_string (string& e) { return "\"" + e + "\""; }
string to_string (char e) { return "\'" + string(1, e) + "\'"; }
string to_string (bool e) { return e ? "true" : "false"; }
template <typename T> string to_string (T e) {
	string s = "[ ";
	for (auto& x : e) s += to_string(x) + " ";
	return s + "]";
}
template <typename U, typename V> string to_string (pair<U, V> e) {
	return "(" + to_string(e.first) + ", " + to_string(e.second) + ")";
}
void dbg_str () { errp(" \n"); }
template <typename U, typename... V> void dbg_str (U u, V... v) {
 	errp(" %s", to_string(u).c_str()); dbg_str(v...);
}
/* --- */
struct Point {
	int x, y, h;
	Point() {}
	Point(int _x, int _y, int _h): x(_x), y(_y), h(_h) {}
	bool operator< (const Point& other) {
		if (h == other.h) {
			return ii(x, y) < ii(other.x, other.y);
		}
		return h < other.h;
	}
};

vector<Point> pts;
int n, cx, cy, ch;

bool can (int tx, int ty, int th) {
	Foz(i, sz(pts)) {
		if (pts[i].h != max(th - abs(pts[i].x - tx) - abs(pts[i].y - ty), 0))
			return false;
	}
	return true;
}

void solve() {
	assert(pts[0].h > 0);
	Foz(x, 101) Foz(y, 101) {
		int h = pts[0].h + abs(pts[0].x - x) + abs(pts[0].y - y);						
		if (can(x, y, h)) {
			cx = x; cy = y; ch = h;
			return;
		}
	}
	assert(1 == 0);
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	/* --- */
	int x, y, h;
	cin >> n;
	Foz(i, n) {
		cin >> x >> y >> h;
		pts.pb({x, y, h});
	}
	sort(all(pts));
	reverse(all(pts));
	solve();
	cout << cx << ' ' << cy << ' ' << ch << '\n';

}



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

#ifndef ONLINE_JUDGE
	#define W(x, y) cerr << "\033[31m" << #x << " = " << x << "\033[0m" << y;
#else
	#define W(x, y)
#endif

#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vii vector<pii>
#define vl vector<ll>
#define vll vector<pll>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define pi acosl(-1)
#define ld long double
#define prime (1000000000 + 7)
#define INF 1000000000

using namespace std;

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

	ll n;
	cin >> n;
	ll res = (n + 0) / 3;
	cout << res << endl;
	
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXN 100100
int n, cnt, k, len;
char s[MAXN];
int main()
{
	scanf("%d",&n);
	scanf("%s",s+1);
	len = strlen(s+1);
	if(len <= n) printf("%s",s+1);
	else 
	{
		for(int i=1;i<=n;i++) printf("%c",s[i]);
		printf("...\n");
	}
	
	return 0;
}

Measured memory_bytes: 3764
N = int(input().strip())
A = list(map(int, input().strip().split()))
B = list(map(int, input().strip().split()))

def calc(a, b, c):
    if a < b:
        b -= a 
        c += a 
        a = 0 
    else:
        a -= b 
        c += b 
        b = 0
    return a, b, c 

c = 0
for i in reversed(range(N)):
    A[i+1], B[i], c = calc(A[i+1], B[i], c)
    A[i], B[i], c = calc(A[i], B[i], c)

print(c)

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

const int maxn = 110000;
const long long inf = (long long)1e18 + 1e9;

long long C[maxn];
int N;

inline void update(int x, long long val) {
	for(; x; x -= x & -x) C[x] = min(C[x], val);
}

inline long long get(int x) {
	long long ret = inf;
	for(; x <= N; x += x & -x) ret = min(ret, C[x]);
	return ret;
}

struct Dist {
	int l, r, c;
	Dist(int l = 0, int r = 0, int c = 0) : l(l), r(r), c(c) {}
} d[maxn];

inline bool operator < (const Dist& lhs, const Dist& rhs) {
	return lhs.l < rhs.l;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, m; cin >> n >> m;
	N = n;
	for(int i = 1; i <= n; ++ i) C[i] = inf;
	update(1, 0);
	for(int i = 0; i < m; ++ i) {
		cin >> d[i].l >> d[i].r >> d[i].c;
	}
	sort(d, d + m);
	int j = 0;
	for(int i = 1; i <= n; ++ i) {
		for(; j < m && d[j].l == i; ++ j) {
			update(d[j].r, get(d[j].l) + d[j].c);
		}
	}
	long long ans = get(n);
	cout << (ans == inf ? -1 : ans) << "\n";
	return 0;
}


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


using namespace std;
typedef long long ll;

int main() {
	int a, b, v;
	scanf("%d %d", &a, &b);
	if (a + b >= a - b) v = a + b;
	else v = a - b;
	(a * b >= v) ? printf("%d", a * b) : printf("%d", v);	
	return 0; 
}

 


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <complex>
#include <cmath>
#include <numeric>
#include <bitset>
#include <functional>

using namespace std;

#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << ": " << arg1 << " |";
  __f(comma + 1, args...);
}

typedef long long int64;
typedef pair<int64, int64> ii;
const int64 INF = 1LL << 60;
const int MOD = 1e9 + 7;

const int N = 1e5 + 10;
vector<ii> a[N];
int64 d[N], e[N];
int dp[N], ep[N];

void dijkstra(int s, int n, int64 d[], int dp[]) {
  fill(d, d + n, INF);
  d[s] = 0;
  dp[s] = 1;
  priority_queue<ii, vector<ii>, greater<ii>> Q;
  Q.push({d[s], s});
  while (!Q.empty()) {
    ii top = Q.top();
    Q.pop();
    int64 u = top.second, dd = top.first;
    if (dd != d[u]) continue;
    for (auto& it : a[u]) {
      int64 v = it.first, cost = it.second;
      if (d[v] > d[u] + cost) {
        d[v] = d[u] + cost;
        dp[v] = dp[u];
        Q.push({d[v], v});
      } else if (d[v] == d[u] + cost) {
        dp[v] = (dp[v] + dp[u]) % MOD;
      }
    }
  }
}

int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  int s, t;
  scanf("%d%d", &s, &t);
  --s; --t;
  while (m--) {
    int x, y, z;
    scanf("%d%d%d", &x, &y, &z);
    --x; --y;
    a[x].push_back({y, z});
    a[y].push_back({x, z});
  }
  dijkstra(s, n, d, dp);
  dijkstra(t, n, e, ep);
  int64 dist = d[t];
  // trace(dist);
  int ret = 0;
  for (int i = 0; i < n; ++i) {
    if (d[i] == INF) continue;
    if (d[i] * 2 == dist) {
      int cur = (int64)dp[i] * ep[i] % MOD;
      // trace(i, cur);
      ret = (ret + (int64)cur * cur) % MOD;
    }
    for (auto& it : a[i]) {
      int j = it.first, cost = it.second;
      if (d[i] + cost + e[j] == dist &&
          d[i] * 2 < dist && d[j] * 2 > dist) {
        int cur = (int64)dp[i] * ep[j] % MOD;
        // trace(i, j, cur);
        ret = (ret + (int64)cur * cur) % MOD;
      }
    }
  }
  ret = ((int64)dp[t] * dp[t] % MOD + MOD - ret) % MOD;
  printf("%d\n", ret);
  return 0;
}


Measured memory_bytes: 18004
n,m = map(int,raw_input().strip().split(' '))
graph = [[] for i in range(n)]
for i in range(m):
    s,t = map(int,raw_input().strip().split(' '))
    graph[s].append(t)
    graph[t].append(s)
 
color = {}
c = 0
for i in range(n):
    if not i in color:
        que = [i]
        color[i] = c
        while len(que) > 0:
            u = que[0]
            for v in graph[u]:
                if not v in color:
                    color[v] = c
                    que.append(v)
            del que[0]
        c += 1
 
 
q = int(raw_input())
for i in range(q):
    s,t = map(int,raw_input().strip().split(' '))
    if color[s] == color[t]:
        print 'yes'
    else:
        print 'no'

Measured memory_bytes: 32076
from functools import reduce
def gcd(a, b):
    while b: a, b = b, a % b
    return a
N, K = map(int, input().split())
A = [int(a) for a in input().split()]
g = reduce(gcd, A)
print("IMPOSSIBLE" if K%g or K > max(A) else "POSSIBLE")

Measured memory_bytes: 14748
#include <bits/stdc++.h>
#include <boost/range/algorithm.hpp>
#include <boost/range/numeric.hpp>
#include <boost/range/irange.hpp>
#include <boost/range/adaptor/indexed.hpp>

using namespace std;
using namespace boost::adaptors;
using namespace std::string_literals;
using ll = int64_t;
using vecint = vector<int>;
using vecll = vector<ll>;
using boost::irange;
constexpr ll MOD = 998244353;

int main()
{
  string s;
  cin>>s;
  int n=s.size();
  int m=2*n;
  vecll count_r(m+1, 0);
  vecll count_b(m+1, 0);
  for (int i:irange(0,n)) {
    switch (s[i]) {
      case '0': 
        count_r[i+1] = count_r[i] + 2;
        count_b[i+1] = count_b[i] + 0;
        break;
      case '1':
        count_r[i+1] = count_r[i] + 1;
        count_b[i+1] = count_b[i] + 1;
        break;
      case '2':
        count_r[i+1] = count_r[i] + 0;
        count_b[i+1] = count_b[i] + 2;
        break;
    }
  }
  for (int i:irange(n,m)) {
    count_r[i+1] = count_r[i];
    count_b[i+1] = count_b[i];
  }
  vector<vecll> dp(m+1, vecll(m+1, 0));
  dp[0][0] = 1;
  for (int i:irange(0,m+1)) {
    for (int j:irange(0,m+1)) {
      int t = i+j;
      if (t > m) break;
      if (i > count_r[t] || j > count_b[t]) continue;
      if (i > 0) dp[i][j] += dp[i-1][j];
      if (j > 0) dp[i][j] += dp[i][j-1];
      dp[i][j] %= MOD;
    }
  }
  cout<<dp[count_r.back()][count_b.back()]<<endl;
  return 0;
}


Measured memory_bytes: 125568
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    int ans=0;
    cin>>s;
    for(int i=0;i<s.size();i++) if(s[i]=='x') ans++;
    if(ans<8)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    return 0;
}

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

int main(){
  int a,b,array[101],Arobot[101],Brobot[101],c=0,i;
  cin>>a>>b;
  for(i=0;i<a;i++){
    cin>>array[i];
    if(array[i]>b-array[i]){
      c+=2*(b-array[i]);
    }else{
      c+=2*array[i];
    }
  }
  cout<<c<<endl;
}

Measured memory_bytes: 256
import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		while (true) {
			String[] str = br.readLine().split(" ");
			int h = Integer.parseInt(str[0]);
			int w = Integer.parseInt(str[1]);
			if (h == 0 & w == 0) {
				break;
			}
			for (int i = 0; i < h; i++) {
				for (int j = 0; j < w; j++) {
					if (i == 0 | i == h - 1 | j == 0 | j == w - 1) {
						System.out.print("#");
						continue;
					}
					System.out.print(".");
				}
				System.out.println("");
			}
			System.out.println("");
		}
	}
}

Measured memory_bytes: 32224
#include <iostream>
using namespace std;
int ATCG_FUNCTION(string str, int i);

int main()
{
    string str;
    int max = 0;
    int sum = 0;

    cin >> str;

    for(int i = 0; str[i] != '\0'; i++) {
        sum += ATCG_FUNCTION(str, i);
            if(sum > max) {
                max = sum;
            }
            if(ATCG_FUNCTION(str, i) == 0) {
                sum = 0;
            }
    }

    cout << max;

    return 0;
}

int ATCG_FUNCTION(string str, int i) {
    switch(str[i]) {
            case 'A':
                return 1;
                break;
            case 'T':
                return 1;
                break;
            case 'C':
                return 1;
                break;
            case 'G':
                return 1;
                break;
            default:
                return 0;
        }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define irep(i, n) for (int i = n; i >= 0; i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = 1 << 30;
 
int main() {
	int n, k;
	cin >> n >> k;
	int h[20];
	rep(i,n) cin >> h[i];

	ll ans = 1e12;
	rep(s, 1<<n) {
		ll sum = 0, now = 0;
		int can_see = 0;

		rep(i,n) {
			if (now < h[i]) {now = h[i]; can_see++;} 		
			else if (s>>i&1) {
				sum += now - h[i] + 1;
				now++;
				can_see++;
			}
		}
		if (can_see>= k) ans = min(ans, sum);
	} 
	cout << ans << endl;
	return 0;
}

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

using namespace std;

int main(int argc, char *argv[])
{
    
    
    cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);

    int n,m;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        m = i;
        if (i%3==0) {
            cout << ' ' << i;
            continue;
        }
        while (m) {
            //cout << i << endl;
            if (m%10 ==3) {
                cout << ' ' << i;
                break;
            }
            m /= 10;
        }
    }
    cout << endl;
    
    return 0;
}



Measured memory_bytes: 3140