akhauriyash/Code-Regression huggingface dataset:
line = input()
for _ in range(int(input())):
    x = input().split()
    order = x[0]
    a = int(x[1])
    b = int(x[2])+1
    if order == "print":
        print(line[a:b])
    elif order == "reverse":
        line = line[:a] + line[a:b][::-1] + line[b:]
    elif order == "replace":
        line = line[:a] + x[3] + line[b:]



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

string lcs(string l,string r){
    string k;
    int h=0;
    for(int i=0;i<l.size();i++){
        for(int j=h;j<r.size();j++){
            if(l[i]==r[j]){
                k.push_back(l[i]);
                h=j+1;
                break;
            }
        }
    }
    return k;
}

int main(void){
    ll n;cin>>n;
    vector<string> ss(n);
    rep(i,n)cin>>ss[i];
    rep(i,n)sort(ss[i].begin(),ss[i].end());
    string c=ss[0];
    for(int i=1;i<n;i++) c=lcs(c,ss[i]);
    cout<<c<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define repr(i, n) REPR(i, n, 0)
#define REPR(i, s, e) for(int i=(int)(s-1); i>=(int)(e); i--)
#define pb push_back
#define all(r) r.begin(),r.end()
#define rall(r) r.rbegin(),r.rend()
#define fi first
#define se second

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

const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const double EPS = 1e-8;

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

#define DEBUG_MODE
#ifdef DEBUG_MODE
#define dump(x) cout << #x << " : " << x << " "
#define dumpL(x) cout << #x << " : " << x << '\n'
#define LINE cout << "line : " << __LINE__ << " "
#define LINEL cout << "line : " << __LINE__ << '\n'
#define dumpV(v) cout << #v << " : ["; for(auto& t : v) cout << t << ", "; cout<<"]" << " "
#define dumpVL(v) cout << #v << " : ["; for(auto& t : v) cout << t << ", "; cout<<"]" << endl
#define STOP assert(false)
#else
#define dump(x) 
#define dumpL(x) 
#define LINE 
#define LINEL 
#define dumpV(v) 
#define dumpVL(v) 
#define STOP assert(false)
#endif
#define mp make_pair
 
namespace std {
template<class S, class T>
ostream &operator <<(ostream& out, const pair<S, T>& a) {
    out << '(' << a.fi << ", " << a.se << ')';
    return out;
}
}

int main(){
    ll n;
    cin >> n;
    ++n;
    vl a(n);
    rep(i, n) cin >> a[i];
    if(n == 1) {
        cout << (a[0] == 1 ? 1: -1) << '\n';
        return 0;
    }
    vl b(n);
    // b.back() = a.back();
    // repr(i, n -1) {
    //     b[i] = b[i+1] + a[i];
    //     if(i < 61) {
    //         chmin(b[i], 1LL<<i);
    //     }
    // }
    b[0] = 1;
    rep(i, n-1) {
        b[i+1] = (i < 61) ? 1LL<<(i+1) : INF;
        chmin(b[i+1], (b[i] - a[i]) * 2);
    }
    if(b.back() < a.back()) {
        cout << -1 << '\n';
        return 0;
    }
    chmin(b.back(), a.back());
    repr(i, n-1) {
        chmin(b[i], a[i]+b[i+1]);
    }
    // dumpVL(b);
    rep(i, n) {
        if(b[i] <= 0) {
            cout << -1 << '\n';
            return 0;
        } 
    }
    // if(b.back() != a.back()) {
    //     cout << -1 << '\n';
    //     return 0;
    // }
    // rep(i, n-1) {
    //     int mi = b[i] - b[i+1];
    //     int ma = b[i] - (b[i+1]+1)/2;
    //     if(mi <= a[i] && a[i] <= ma) ;
    //     else {
    //         cout << -1 << '\n';
    //         return 0;
    //     }
    // }
    cout << accumulate(all(b), 0LL) << '\n';
    // dumpVL(b);
    return 0;
}

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

const int MOD = 1e9 + 7;

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

    vector<int> dp(n + 1);
    dp[0] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= i - 3; ++j) {
            dp[i] += dp[j];
            dp[i] %= MOD;
        }
    }

    cout << dp[n] << endl;

    return 0;
}

Measured memory_bytes: 3632
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<set>

using namespace std;

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

	char n = N[N.length() - 1];

	if (n == '2' || n == '4' || n == '5' || n == '7' || n == '9') {
		cout << "hon" << endl;
	}
	else if (n == '0' || n == '1' || n == '6' || n == '8') {
		cout << "pon" << endl;
	}
	else {
		cout << "bon" << endl;
	}
}


Measured memory_bytes: 3628
import sys

input = sys.stdin.readline


def main():
    A, B, C, D, E, F = [int(x) for x in input().split()]

    b = [False] * 31
    b[A] = True
    b[B] = True

    for i, v in enumerate(b):
        if v:
            if i + A <= 30:
                b[i + A] = True
            if i + B <= 30:
                b[i + B] = True

    sugar = [False] * 3001
    sugar[C] = True
    sugar[D] = True

    for i, v in enumerate(sugar):
        if v:
            if i + C <= 3000:
                sugar[i + C] = True
            if i + D <= 3000:
                sugar[i + D] = True

    ans1 = A * 100
    ans2 = 0

    for i, v in enumerate(b):
        if v:
            for j, s in enumerate(sugar):
                if s:
                    if ans2 / (ans1 + ans2) < j / (i * 100 + j) <= E / (100 + E) and i * 100 + j <= F:
                        ans1 = i * 100
                        ans2 = j

    print(ans1 + ans2, ans2)





if __name__ == '__main__':
    main()


Measured memory_bytes: 3316
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
const ll inf = numeric_limits<ll>::max()/3;

int main(void){
  string s;
  cin >> s;
  int cnt[30];
  fill(cnt,cnt+30,0);
  for(int i = 0;i < (int)s.size();++i){
    ++cnt[s[i] - 'a'];
  }
  for(int i = 0;i < 26;++i){
    if(cnt[i] == 0){
      cout << s << (char)('a' + i) << endl;
      return 0;
    }
  }
  for(int i = (int)s.size()-1;i >= 0;--i){
    --cnt[s[i] - 'a'];
    for(int j = (int)(s[i] - 'a') + 1;j < 26;++j){
      if(cnt[j] == 0){
        cout << s.substr(0,i) << (char)('a' + j) << endl;
        return 0;
      }
    }
  }
  puts("-1");
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<climits>
#include<queue>
#include <utility>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)

typedef queue<int> IntQueue;

int H,W;
//const int MAX=64;
//int c[MAX][MAX];
//int d[MAX][MAX];

void BFS(){
  cin>>H>>W;
  int c[H][W];
  int d[H][W];
  IntQueue Qx;
  IntQueue Qy;
  char a;
  rep(i,H){
    rep(j,W){
      cin>>a;
      if (a=='#'){
        c[i][j]=1;
        d[i][j]=0;
        Qx.push(i);
        Qy.push(j);
      }
      else c[i][j]=0;
    }
  }
  int ux,uy;
  while (!Qx.empty()){
    ux=Qx.front();
    uy=Qy.front();
    Qx.pop();
    Qy.pop();
    IntQueue adjx;
    IntQueue adjy;
    int px[4]={0,1,0,-1};
    int py[4]={1,0,-1,0};
    int push_cnt=0;
    int vx,vy;
    rep(i,4){
      vx=ux+px[i];
      vy=uy+py[i];
      if (vx>=0 && vx<H && vy>=0 && vy<W){
        adjx.push(vx);
        adjy.push(vy);
        push_cnt++;
      }
    }
    rep(i,push_cnt){
      vx=adjx.front();
      vy=adjy.front();
      adjx.pop();
      adjy.pop();
      if(c[vx][vy]==0){
        c[vx][vy]=1;
        d[vx][vy]=d[ux][uy]+1;
        Qx.push(vx);
        Qy.push(vy);
      }
    }
  }
  int max_d=0;
  rep(i,H){
    rep(j,W){
      if (max_d<d[i][j])max_d=d[i][j];
    }
  }
  cout<<max_d<<endl;
  return;
}

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


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

int main() {
  int s;
  cin >> s;
  int s1 = s / 100;
  int s2 = (s - (s1 * 100)) / 10;
  int s3 = s - (s1 * 100) - (s2 * 10);
  cout << s1 + s2 + s3 << endl;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void) {
	int x[10010], i = 0, a;
	while (1) {
		i++;
		cin >> x[i];
		if (x[i] == 0) {
			break;
		}
	}
	a = i;
	for (a = 1; a <= i-1; a++) {
		cout << "Case " << a << ": " << x[a] << endl;
	}
	return 0;
}


Measured memory_bytes: 3016
#include <bits/stdc++.h>
#include <vector>
#include <cmath>
#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 REPR(i, n) for (int i = (n)-1; i >= 0; --i)
#define REPR2(i, m, n) for (int i = (n)-1; i >= (m); --i)
#define REPx(x, a) for(auto x : a)
#define ALL(a) a.begin(), a.end()
#define SORT(a) sort(ALL(a))
#define SORTR(a) sort(ALL(a), greater<int>())
#define REVERSE(a) reverse(ALL(a))
#define bit_search(bit, n) REP(bit, 1<<(n))
#define bit_check(bit, i) (bit>>(i)) & 1
#define setpre(n) fixed << setprecision((n))
#define UNIQUE(a) do {SORT(a); (a).erase(unique(ALL(a)), (a).end());} while(0)
#define MAX(a) *max_element(ALL(a))
#define MIN(a) *min_element(ALL(a))
#define bisect_left(a, x) lower_bound(ALL(a), (x)) - a.begin()
#define bisect_right(a, x) upper_bound(ALL(a), (x)) - a.begin()
#define INPUT(a) REP(i, a.size()) cin >> a[i];
#define INPUTP(a) REP(i, a.size()) cin >> a[i].first >> a[i].second;
#define ENDL cout << endl;
using namespace std;
using LL = long long;
using LD = long double;
using PII = pair<int, int>;
using VPII = vector<PII>;
using PLL = pair<LL, LL>;
using VPLL = vector<PLL>;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<LL>;
using VVLL = vector<VLL>;
using VC = vector<char>;
using VS = vector<string>;
using VB = vector<bool>;
using VD = vector<double>;
const LL INF = 1e18;
const LL MOD = 1e9 + 7;

template<class T> inline bool chmin(T &a, T b){if (a > b) {a = b; return true;} return false;}
template<class T> inline bool chmax(T &a, T b){if (a < b) {a = b; return true;} return false;}

bool check(auto* nn, auto ll, auto vv, auto* mm, auto* aa)
{
  LL a = *nn / ll;
  *mm += a * vv;
  *nn -= a * ll;
  if (*nn == 0)
  {
    chmin(*aa, *mm);
    return true;
  }
  else return false;
}

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  double n;
  VD L = {0.25, 0.5, 1.0, 2.0};
  VLL V(4);
  cin >> V[0] >> V[1] >> V[2] >> V[3] >> n;
  LL ans = INF;
  REP(h, 4) REP(i, 4) REP(j, 4) REP(k, 4)
  {
    if (h != i && h != j && h != k && i != j && i != k && j != k)
    {
      double N = n;
      LL money = 0;
      if (check(&N, L[h], V[h], &money, &ans)) break;
      if (check(&N, L[i], V[i], &money, &ans)) break;
      if (check(&N, L[j], V[j], &money, &ans)) break;
      if (check(&N, L[k], V[k], &money, &ans)) break;
    }
  }
  cout << ans << endl;

  return 0;
}


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

vector<int> num(9);
vector<char> color(9);

bool ok(int i,int j,int k){
    if(color[i] != color[j] || color[j] != color[k]) return false;
    if(num[i] == num[j] && num[j] == num[k]) return true;
    if(num[i]+2 == num[j]+1 && num[j]+1 == num[k]) return true;
    return false;
}


int main(){
    int t;
    cin >> t;
    vector<int> idx(9);
    iota(idx.begin(),idx.end(),0);
    while(t--){
        bool ans = false;
        rep(i,9) cin >> num[i];
        rep(i,9) cin >> color[i];
        do{
            bool res = true;
            rep(i,3){
                res = res && ok(idx[i*3],idx[3*i+1],idx[3*i+2]);
            }
            ans = ans || res;
        }while(next_permutation(idx.begin(),idx.end()));
        cout << (ans ? 1 : 0 ) << endl;
    }
    return 0;
}

/*
Rummy
できるだけ関数化しようと思って連番または全て同じ番号になっているものかどうかを判定する関数を作ろうと思った。
結局ok関数の中身は汚くなったので全体としてはわかりやすくなったと思う。
*/


Measured memory_bytes: 3056
#include <iostream>
#include <time.h>
//#include <conio.h>
#include <algorithm>
using namespace std;

int main()
{
	int n;
	cin >> n;
	int arr[3];
	for (int i = 0; i < 3; i++)
	{
		arr[i] = n % 10;
		n /= 10;
	}
	if (arr[0] == arr[2])
		cout << "Yes";
	else cout << "No";
	//_getch();
	return 0;
}

Measured memory_bytes: 256
N = int(input())
def divisor_all(n): # 約数全列挙
    l = [1,n]
    for i in range(2,int(pow(n,1/2))+1):
        if n % i == 0:
            if i == n//i:
                l.append(i)
            else:
                l.append(i)
                l.append(n//i)
    l.sort()
    return l # list
ans = 0
for i in range(1,N+1,2):
    if len(divisor_all(i))==8:
        ans += 1
print(ans)

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

string S;
int N;

int main(){
    cin >> S;
    N = (int)(S.length());
    int children[N];
    for(int i=0;i<N;i++){
      children[i]=0;
    }

    int j=0;
    for(int i=0;i<N;i++){
      if(S[i]=='R'&& i<j){

      }else if(S[i]=='L'&& i>j){

      }else{
        j=i;
        while(S[i]==S[j]){
          if(S[j]=='R'){
            j++;
          }else{
            j--;
          }
        }
      }
      if(i<j){
        if((j-i)%2==1){
          children[j-1]++;
        }else{
          children[j]++;
        }
      }else{
        if((i-j)%2==1){
          children[j+1]++;
        }else{
          children[j]++;
        }
      }
    }



    for(int i= 0;i<N-1;i++){
      cout << children[i] << " ";
    }
    cout << children[N-1];

}


Measured memory_bytes: 1024
s = list(input())
t = list(input())
num = len(t)

fail = 'UNRESTORABLE'
flag = False
ans = []
count_out = 0

for i in range(len(s)):
    start = i
    end = i + len(t)
    if (end > len(s)):
        break
    tar = s[start:end]
    # print(tar)
    index = 0
    name_flag = True

    for a, b in zip(tar, t):
        # print(tar[index])
        if (a == b):
            pass
        elif (a == '?'):
            tar[index] = str(b)
        else:
            name_flag = False
            break

        index += 1

    if (name_flag is False):
        ans.append(['z'] * len(s))
        count_out += 1
    else:
        pre_org = s[:start]
        # pre = pre_org.replace('?', 'a')
        post_org = s[end:]
        # post = post_org.replace('?', 'a')

        # tar_mod = pre + tar + post
        tar_mod = pre_org + tar + post_org
        ans.append(tar_mod)

# print(ans)
if (count_out == (len(s) - len(t) + 1)):
    print(fail)
else:
    ans_s = sorted(ans)
    aa = ans_s[0]
    a2 = ''.join(aa)
    a3 = a2.replace('?', 'a')
    print(a3)


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

int main() {
	int n,m;cin>>n>>m;
	vector<int> a(m),b(m),c(m);
	int def=1;
	for(int i=0;i<9;i++){
		def*=10;
	}
	vector<vector<int>> v(n,vector<int>(n,def));
	for(int i=0;i<n;i++){
		v[i][i]=0;
	}
	for(int i=0;i<m;i++){
		cin>>a[i]>>b[i]>>c[i];
		a[i]--;
		b[i]--;
		v[a[i]][b[i]]=c[i];
		v[b[i]][a[i]]=c[i];
	}
	for(int k=0;k<n;k++){
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				if(v[i][j]>v[i][k]+v[k][j]){
					v[i][j]=v[i][k]+v[k][j];
					v[j][i]=v[i][j];
				}
			}
		}
	}
	vector<int> l(m,0);
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(i==j)continue;
			for(int k=0;k<m;k++){
				if(a[k]==i){
					if(v[i][j]==c[k]+v[j][b[k]]){
						l[k]=1;
					}
				}
				if(b[k]==i){
					if(v[i][j]==c[k]+v[j][a[k]]){
						l[k]=1;
					}
				}
				if(a[k]==j){
					if(v[i][j]==c[k]+v[i][b[k]]){
						l[k]=1;
					}
				}
				if(b[k]==j){
					if(v[i][j]==c[k]+v[i][a[k]]){
						l[k]=1;
					}
				}
			}
		}

	}
	int ans=m;
	for(int i=0;i<m;i++){
		ans-=l[i];
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
using namespace std;
typedef long long int ll;

ll mod=1e9+7;

int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int n; cin >> n;
	vector<ll> aa(n);
	ll ans=1;
	for(int i=0;i<n;i++){
		cin >> aa[i];
	}
	int a[3];
	for(int i=0;i<3;i++){
		a[i]=0;
	}
	for(int i=0;i<n;i++){
		ll cnt=0;
		for(int j=0;j<3;j++){
			if(a[j]==aa[i])cnt++;
		}
		if(cnt==0){
			cout << 0 << endl;
			return 0;
		}
		ans*=cnt;
		ans%=mod;
		for(int j=0;j<3;j++){
			if(a[j]==aa[i]){
				a[j]++;
				break;
			}
		}
		sort(a,a+3);
	}
	cout << ans << endl;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define rep(i,n) for(ll i=0;i<n;++i)
#define ocut cout
#define ouct cout
#define itn int

struct Union{
  vector<ll> par;
  Union(ll a){
  par=vector<ll>(a,-1);
  }
  ll find(ll a){
    if(par[a]<0){
      return a;
    }
    else{
      return par[a]=find(par[a]);
    }
  }
  bool same(ll a,ll b){
    return (find(a)==find(b));
  }
  ll size(ll a){
    return -par[find(a)];
  }
  void unite(ll a,ll b){
    ll c=find(a),d=find(b);
    if(c==d)
      return;
    if(size(c)<size(d)){
      swap(c,d);
    }
    par[c]+=par[d];
    par[d]=c;
  }
};
ll euclidean_gcd(ll a, ll b) {
  if(a < b) return euclidean_gcd(b, a);
  ll r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}
ll euclidean_lcm(ll a, ll b) {
  return a/euclidean_gcd(a,b)*b;
}

ll binary(ll bina){
    ll ans = 0;
    for (ll i = 0; bina>0 ; i++)
    {
        ans += bina%2;
        bina = bina/2;
    }
    return ans;
}
void revStr(char* str){
	int size = strlen(str);
	int i,j;
	char tmp = {0};
	
	for(i = 0, j = size - 1; i < size / 2; i++, j--){
		tmp = str[i];
		str[i] = str[j];
		str[j] = tmp;
	}
	return;	
}
int main(void){
  ll n;
  cin >> n;
  ll l[n],c=0;
  rep(i,n)cin >> l[i];
  for(ll i=0;i<n;i++){
    for(ll j=i+1;j<n;j++){
      for(ll k=j+1;k<n;k++){
        if(l[i]!=l[j]&&l[j]!=l[k]&&l[i]!=l[k]&&l[i]+l[j]>l[k]&&l[i]+l[k]>l[j]&&l[k]+l[j]>l[i])c++;
      }
    }
  }
  cout << c;
}

Measured memory_bytes: 3520
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <stack>
#include <string>
#include <vector>

#define REP(i, n) for(int i = 0; i < n; ++i)
using namespace std;
using LLONG = long long;
const LLONG MOD = 1000000007;

int main()
{
	string s; cin >> s;
	map<char, int> ch2NumMap;
	for (const char ch : s)
	{
		++ch2NumMap[ch];
	}
	// 26文字以下ならば，使われていない文字の内，もっとも若い文字を後ろにつければよい
	if (s.length() < 26)
	{
		for (char ch = 'a'; ch <= 'z'; ++ch)
		{
			if (ch2NumMap.count(ch) == 0)
			{
				cout << s + ch << endl;
				return 0;
			}
		}
	}
	// 26文字のときの例外ケース
	else if (s == "zyxwvutsrqponmlkjihgfedcba")
	{
		cout << -1 << endl;
	}
	// それ以外の26文字のとき，後ろを削りながら文字を進めて
	// 多彩になる文字列を探す
	else
	{
		int len = s.length();
		for (int i = len - 1; i >= 0; --i)
		{
			// 後ろの文字を削り，先の文字に進めていく
			char back = s.back();
			s.pop_back();
			ch2NumMap[back] = 0;
			for (char ch = back + 1; ch <= 'z'; ++ch)
			{
				// 既に削られた文字に当たった場合，
				// 最後尾をその文字に置換することで多彩になる
				if (ch2NumMap[ch] == 0)
				{
					cout << s + ch << endl;
					return 0;
				}
			}
		}
	}
}


Measured memory_bytes: 3580
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define dbug(x) cout<<#x<<"="<<x<<endl
using namespace std;
template <typename T> void read(T &t) {
	t=0; char ch=getchar(); int f=1;
	while ('0'>ch||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
	do {(t*=10)+=ch-'0';ch=getchar();} while ('0'<=ch&&ch<='9'); t*=f;
}
int n,ans;
char s[5010];
int dp[5010][5010];
int main() {
	//freopen("1.txt","r",stdin);
	read(n); scanf("%s",s+1);
	for (int i=1;i<=n;i++)
	for (int j=i;j<=n;j++) {
		if (s[i]==s[j]) dp[i][j]=dp[i-1][j-1]+1;
		ans=max(ans,min(dp[i][j],j-i));
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 96896
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define ull unsigned long long
#define db long double
#define pb push_back
#define ppb pop_back
#define F first
#define S second
#define mp make_pair
#define all(x) (x).begin(), (x).end()
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef vector <int> vi;
typedef vector <ll> vll;



int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	#ifdef LOCAL
		freopen("input.txt", "r", stdin);
	#endif
	
	int k, a, b;
	cin >> k >> a >> b;
	if (b / k - (a - 1) / k > 0) {
		cout << "OK";
	}	else {
		cout << "NG";
	}
}


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

int main(){
	vector<int> a(3);
	for(int &i: a) cin >> i;
	sort(a.begin(), a.end());
	if(a[0] == a[1]){
		if(a[0] != a[2]) cout << "Yes" << endl;
		else cout << "No" << endl;
	}else{
		if(a[1] == a[2]) cout << "Yes" << endl;
		else cout << "No" << endl;
	}
	return 0;
}


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

#define rep(i,n) for(int i = 0; i < (n); i++)
#define rrep(i,n) for(int i = (n)-1; i >= 0; i--)
#define rep1(i,n) for(int i = 1; i <= (n); i++)
#define rrep1(i,n) for(int i = (n); i > 0; i--)

#define ll long long
#define pi pair<int, int>
#define pll pair<ll, ll>

#define MOD 1000000007
#define INF 1000000000000000LL

using namespace std;

int main(){
  int x;cin>>x;
  cout<<!x<<endl;

  return 0;
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
#define REP(i, a, b) for (long long i = a; i <= b; ++i)
#define PER(i, a, b) for (long long i = a; i >= b; --i)
#define lyj 1000000007
#define ll long long
using namespace std;

ll n, a, b;

inline ll read(){
	ll s = 0, w = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9'){
		if (ch == '-') w *= -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9'){
		s = s * 10 + ch - '0';
		ch = getchar();
	}
	return s * w;
}

inline ll ksm(ll c, ll d){
	ll sum = 1;
	for (; d; d >>= 1, c = c * c % lyj)
		if (d & 1) sum = sum * c % lyj;
	return sum;
}

inline ll xcj(ll n, ll m){
	ll a1 = 1, a2 = 1;
	PER(i, n, n - m + 1) a1 = a1 * i % lyj;
	REP(i, 2, m) a2 = a2 * i % lyj;
	return a1 * ksm(a2, lyj - 2) % lyj;
}

inline void work(){
	n = read(), a = read(), b = read();
	printf("%lld\n", (ksm(2, n) - 1 - xcj(n, a) - xcj(n, b) + lyj + lyj) % lyj);
}

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

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


struct ST {
	int x;
	int y;
	int c;
};

char map[1000 + 10][1000 + 10];

bool wen[1000 + 10][1000 + 10] = { 0 };

int main()
{
	int ly, lx, n;

	ST m, tm;

	queue<ST> qu;

	int gy[] = {1,0,-1,0};
	int gx[] = {0,1,0,-1};

	char G[10 + 5] = { '0','1','2','3','4','5','6','7','8','9' };

	int sum = 0;
	int sy, sx;
	int i, j;

	cin >> ly >> lx >> n;

	for (i = 1; i <= ly; i++)
	{
		cin >> map[i] + 1;

		map[i][0] = 'X';
		map[i][lx + 1] = 'X';

		for (j = 1; j <= lx; j++)
		{
			if (map[i][j] == 'S')
			{
				sy = i;
				sx = j;
			}
		}
	}
	for (i = 0; i <= lx + 1; i++)
	{
		map[0][i] = 'X';
		map[ly + 1][i] = 'X';
	}

	m.y = sy;
	m.x = sx;
	m.c = 0;

	qu.push(m);

	for (i = 1; i <= n; i++)
	{
		while (!qu.empty())
		{
			m = qu.front();

			qu.pop();

			if (wen[m.y][m.x])
			{
				continue;
			}
			wen[m.y][m.x] = true;

			if (map[m.y][m.x] == G[i])
			{
				sy = m.y;
				sx = m.x;
				sum += m.c;

				while (!qu.empty())
				{
					qu.pop();
				}
				memset(wen, 0, sizeof(wen));

				m.c = 0;

				qu.push(m);

				break;
			}

			for (j = 0; j < 4; j++)
			{
				tm.y = m.y + gy[j];
				tm.x = m.x + gx[j];
				tm.c = m.c + 1;

				if (map[tm.y][tm.x] != 'X' && !wen[tm.y][tm.x] )
				{
					qu.push(tm);
				}
			}
		}
	}

	cout << sum << endl;

	return 0;
}

Measured memory_bytes: 5036
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<climits>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<bitset>
#include<iomanip>
using namespace std;

#define rep(i,j,n) for(int i=(j);i<(n);++i)
#define erep(i,j,n) for(int i=(j);i<=(n);++i)
#define all(i) i.begin(),i.end()
#define rall(i) i.rbegin(),i.rend()
#define INF 1e9
const int mod = 1e9 + 7;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;
typedef pair<int, int> pi;
typedef long long i64;

int main() {
	string s;
	cin >> s;

	i64 sum = stol(s);
	rep(bit, 1, 1 << (s.size() - 1)) {
		int pos = 0;
		rep(i, 0, s.size() - 1) {
			if (bit&(1 << i)) {
				string t = s.substr(pos, i - pos + 1);
				sum += stol(t);
				pos = i + 1;
			}
		}
		sum += stol(s.substr(pos));
	}
	cout << sum << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define OUTOFRANGE(y,x,h,w) (y<0||x<0||y>=h||x>=w)
#define dump(...)
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
#define INF (1001001001)
#define INFLL (1001001001001001001ll)
template<class T> ostream& operator << (ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v)) os<<*i<<(i==end(v)-1?"":" "); return os; }
template<class T> istream& operator >> (istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i; return is; }
template<class T> istream& operator >> (istream &is, pair<T,T> &p) {
    is>>p.first>>p.second; return is; }
template<class T> bool chmax(T &a,const T &b) {if(a<b) {a=b;return 1;} return 0;}
template<class T> bool chmin(T &a,const T &b) {if(b<a) {a=b;return 1;} return 0;}
template <class T> using heap = priority_queue<T,vector<T>,greater<T>>;
//------------------------------------------------------------------------------
struct before_main_function {
    before_main_function() {
        #ifdef int
            #undef INF
            #define INF INFLL
            #define stoi stoll
        #endif
        cin.tie(0);ios::sync_with_stdio(false);
        cout<<setprecision(15)<<fixed;
        #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

int dp[1001][1001];
signed main() {
    REP(i,1001) REP(j,1001) dp[i][j]=INF;
    int n,m;
    cin>>n>>m;
    vector<int> d(n),c(m);
    cin>>d>>c;
    dp[0][0]=0;
    REP(i,n) {
        REP(j,m) {
            if(dp[i][j]!=INF) {
                chmin(dp[i][j+1],dp[i][j]);
                chmin(dp[i+1][j+1],dp[i][j]+d[i]*c[j]);
            }
        }
    }
    int ans=INF;
    REP(i,m+1) {
        chmin(ans,dp[n][i]);
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 11036
from collections import defaultdict
import math

def get_sieve_of_eratosthenes(n):
  prime = []
  limit = math.sqrt(n)
  data  = list(range(2, n+1))
  while True:
    p = data[0]
    if limit <= p:
      return prime + data
    prime.append(p)
    data =  [e for e in data if e % p != 0]


max_value = 10**5

is_prime = defaultdict(bool)

prime_list = get_sieve_of_eratosthenes(max_value)

for i in prime_list:
  is_prime[i] = True
  
a = [0]*(max_value)
for i in range(3, max_value, 2):
  if is_prime[i]& is_prime[int((i+1)/2)]:
    a[i] = 1

b = [0]*(max_value+1)
for i in range(max_value):
  b[i+1] = b[i] + a[i]

Q = int(input())
for _ in range(Q):
  l, r = map(int, input().split())
  print(b[r+1] - b[l])

Measured memory_bytes: 13764
n, k, q = (int(i) for i in input().split())
a = [k]*n
d = [0] + [a[i]-a[i-1] for i in  range(1,n)]+[0]
for i in range(q):
  x = int(input())-1
  d[0]-=1
  d[x]+=1
  d[x+1]-=1
  d[n]+=1
a[0]+=d[0]
for i in range(1,n): a[i] = a[i-1]+d[i]
for i in range(n): print("Yes" if a[i]>0 else "No")


Measured memory_bytes: 8656
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <cstdio>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <cmath>
#include <map>
#include <utility>
#include <set>
#include <functional>
#include <numeric>
#define rep(i,a) for( int i = 0; i != (a); ++i )
#define repd(i,a) for( int i = (a); i >= 0; --i )
#define repi(i,a,b) for( int i = (a); i != (b); ++i )
using namespace std;
typedef unsigned long long ull;

int n, m;
std::string s;
int cnt[1000000];
void solve(std::string s){
	memset(cnt, 0, sizeof(cnt));
	for (int i = m-3; i >= 0; --i){
		if (s[i] == 'I' && s[i + 1] == 'O' && s[i + 2] == 'I')cnt[i]=cnt[i+2]+1;

	}
	int ans = 0;
	for (int i = 0; i < m; ++i){
		if (cnt[i] >= n)ans++;
	}
	printf("%d\n", ans);
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	while (std::cin >> n, n){
		std::cin >> m;
		std::cin >> s;
		solve(s);
	}
	//system("pause");
	return 0;

}

Measured memory_bytes: 7076
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <map>
#include <cmath>

using namespace std;

#define int long long

signed main() {
    int n;
    cin >> n;
    vector<int> p(n), q(n);
    for(int i = 0; i < n; i++) cin >> p[i];        
    for(int i = 0; i < n; i++) cin >> q[i];

    vector<int> r = p;
    sort(r.begin(), r.end());

    int a = 0;
    int b = 0;
    int cnt = 0;

    do {
        if(p == r) a = cnt;
        if(q == r) b = cnt;
        cnt++;    
    } while (next_permutation(r.begin(), r.end()));

    cout << abs(a - b) << endl;
    return 0;
}

Measured memory_bytes: 256
// clang-format off
#include <bits/stdc++.h>

#define mp make_pair
#define fst first
#define snd second
#define forn(i,n) for (int i = 0; i < int(n); i++)
#define forn1(i,n) for (int i = 1; i <= int(n); i++)
#define popcnt __builtin_popcount
#define ffs __builtin_ffs
#define ctz __builtin_ctz
#define clz __builtin_clz
#define all(a) (a).begin(), (a).end()
 
using namespace std;

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
using pil = pair<int,ll>;
using pll = pair<ll,ll>;
template <typename T> using vec = vector<T>;
using vi = vec<int>;
using vl = vec<ll>;
template <typename T> using que = queue<T>;
template <typename T> using deq = deque<T>;

template <typename T> T id(T b) {return b;};
template <typename T> void chmax(T &x, T y) {if (x < y) x = y;}
template <typename T> void chmin(T &x, T y) {if (x > y) x = y;}
template <typename S, typename K> bool contains(S &s, K k) { return s.find(k) != s.end(); }
void fastio() { ios_base::sync_with_stdio(false); cin.tie(nullptr); }
constexpr ll TEN(int n) { if (n == 0) return 1LL; else return 10LL*TEN(n-1); }
// clang-format on

int h, w, k;
string grid[10];

bool check(vi group) {
    bool ok = true;
    for (int x : group) {
        ok &= x <= k;
    }
    return ok;
}

int main() {
    fastio();

    cin >> h >> w >> k;
    forn(i, h) cin >> grid[i];

    int ans = INT_MAX;
    for (int b = 0; b < (1 << (h - 1)); b++) {
        int temp = popcnt(b);
        vec<int> group(popcnt(b) + 1, 0);

        for (int i = 0; i < w; i++) {
            int g = 0;
            for (int j = 0; j < h; j++) {
                if (grid[j][i] == '1') {
                    group[g]++;
                }
                if ((b >> j) & 1) g++;
            }

            bool ok = check(group);

            if (!ok) {
                temp++;
                group = vec<int>(popcnt(b) + 1, 0);
                int g = 0;
                for (int j = 0; j < h; j++) {
                    if (grid[j][i] == '1') {
                        group[g]++;
                    }
                    if ((b >> j) & 1) g++;
                }
            }

            if (!check(group)) {
                temp = INT_MAX;
                break;
            }
        }

        chmin(ans, temp);
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,  n) for (int i  =  0; i < (int)(n); ++i)
#define REPR(i,  n) for (int i  =  n - 1; i >= 0; --i)
using namespace std;
#define int long long int
//------------ATCODER TEMPLATE-------------

signed main() {
  int A, B; cin >> A >> B;
  cout << A * B << endl;
  return 0;
}


Measured memory_bytes: 3588
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int H = sc.nextInt();
		int N = sc.nextInt();
		long A[] = new long[N];
		long B[] = new long[N];
		long mana[] = new long[H];
		for (int i=0;i<N;i++) {
			A[i] = sc.nextLong();
			B[i] = sc.nextLong();
		}
		long min = Long.MAX_VALUE;
		for (int i=0;i<N;i++) {
			if (A[i]>=H) {
				if (B[i]<min) {
					min = B[i];
				}
			} else {
				if (mana[(int)A[i]]==0||mana[(int)A[i]]>B[i]) {
					mana[(int)A[i]]=B[i];
				}
			}
		}
		for (int i=1;i<H;i++) {
			if (mana[i]==0)
				continue;
			for (int j=0;j<N;j++) {
				if (A[j]+i>=H) {
					if (B[j]+mana[i]<min) {
						min = B[j]+mana[i];
					}
				} else {
					if (mana[(int)A[j]+i]==0||mana[(int)A[j]+i]>B[j]+mana[i]) {
						mana[(int)A[j]+i]=B[j]+mana[i];
					}
				}
			}
		}
		System.out.println(min);
	}
}

Measured memory_bytes: 26112
N = int(input())
a = list(map(int,input().split()))
print(' '.join(map(str,a)))
for i in range(1,N):
    v = a[i]
    j = i - 1
    while j >= 0 and a[j] > v:
        a[j + 1] = a[j]
        j-=1
        a[j + 1] = v
    print(' '.join(map(str,a)))



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

using namespace std;


int main() {
	int N, M;

	cin >> N >> M;

	vector< vector< int> > sw_eb(N, vector<int> (0, 0));
	for (int i = 0; i < M; i++) {
		int k;
		cin >> k;
		for (int j = 0; j < k; j++) {
			int s;
			cin >> s;
			s--;
			sw_eb[s].push_back(i);
		}
	}

	int p[M];

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

	int total = 0;


	for (int i = 0; i < 1 << N; i++) {
		vector<int> eb_on(M,0);
		int cur = i;
		int sw_index = 0;
		while(cur > 0) {
			if ((cur & 1) == 1) {
				for (int c : sw_eb[sw_index]) {
					eb_on[c]++;
				}
			}
			cur /= 2;
			sw_index ++;


		}

		int ok = true;
		for (int j = 0; j < M; j++) {
			if (eb_on[j] % 2 != p[j]) {
				ok = false;
				break;
			}
		}
		if (ok) {
			total++;
		}

	}
	cout << total << endl;

	return 0;
}

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

bool is_integer( double x ){
  return floor(x)==x;
}

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

    for(int i=N;i>=1;i--){
        if(is_integer(sqrt(i))){
            cout << i << endl;
            return 0;
        }
    }
   
}

Measured memory_bytes: 3608
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;	

int main() {
    int a, b;
    cin >> a >> b;
    if (a + b >= 10) {
        cout << "error" << endl;
    }
    else {
        cout << a + b << endl;
    }
}


Measured memory_bytes: 3564
#include<iostream>
using namespace std;
int n,s;
const long long mod=998244353;
int a[5000];
int dp[5000];
long long res=0;
int main()
{
	cin >> n >> s;
	for(int i=1;i<=n;i++) cin >> a[i];
	for(int i=1;i<=n;i++){
		dp[0]++;
		for(int j=s;j>=a[i];j--){
			dp[j]=(dp[j]+dp[j-a[i]])%mod;
		}
		res=(res+dp[s])%mod;
	}
	cout << res;
	return 0;
}

Measured memory_bytes: 256
n = int(input())
l = []
for i in range(n):
    w = input()
    l.append(w)
l.append(w[-1])
f = l[0]
ls = set(l)
fff=0
if len(l) != len(ls):
    fff = 1
    print("No")
else:
    first = f[0]
    for i in range(n):
        if l[i][-1] == l[i+1][0]:
            continue
        else:
            fff = 1
            print("No")
            break
if fff ==0:
    print("Yes")

Measured memory_bytes: 3064
N = int(input())
ans = [0] * N
for i in range(1, 101):
    for j in range(1, 101):
        for k in range(1, 101):
            tmp = i**2+j**2+k**2+i*j+j*k+k*i
            if tmp <= N:
                ans[tmp-1] += 1
print(*ans, sep='\n')

Measured memory_bytes: 73928
/*1803115*/
#include <stdio.h>
int main()
{
    char ch;
    int x,c[26]= {0};

    while(scanf("%c",&ch)!=EOF)
    {
        if(ch>='A' && ch<='Z')
        {
            x=ch-'A';
            c[x]+=1;
        }
        else if(ch>='a' && ch<='z')
        {
            x=ch-'a';
            c[x]+=1;
        }
    }

    for(x=0,ch='a'; x<26; x++,ch++)
    {
        printf("%c : %d\n",ch,c[x]);
    }
    return 0;
}



Measured memory_bytes: 2128
l,r = map(int,input().split())
ans = l*(l+1)
if int(l/2019) < int(r/2019):
    print(0)
else:
    for i in range(l,r):
        for j in range(i+1,r+1):
            mod = (i*j)%2019
            if mod < ans:
              ans = mod
            if ans == 0:
                break
    print(ans)



Measured memory_bytes: 3060
#include <iostream>
#include <string>
#define LL long long

int main(){
	char strs[3][3];
	for(int i=0;i<3;i++)std::cin >> strs[i];

	std::cout << strs[0][0] << strs[1][1] << strs[2][2] << std::endl;
	return 0;
}


Measured memory_bytes: 256
#ifndef _WIN32
#include<iostream>
#endif

using namespace std;
#include<string>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<map>


#define FOR(i,bg,ed) for(int i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define SR first.first
#define SC first.second
#define GR second.first
#define GC second.second
typedef vector<int> V;
typedef vector<V> VV;

template<typename T>
bool chmin(T &l, T r) {
	bool f = l > r; if (f)l = r; return f;
}
template<typename T>
bool chmax(T &l, T r) {
	bool f = l < r; if (f)l = r; return f;
}
VV wrap(VV vs, int c) {
	int R = vs.size();
	int C = vs[0].size();
	VV ret(R + 2, V(C + 2, c));
	REP(i, R)REP(j, C)ret[i + 1][j + 1] = vs[i][j];
	return ret;
}
const int dr[] = { 0,0,-1,1 ,1,1,-1,-1 };
const int dc[] = { -1,1,0,0, -1,1,-1,1 };
vector<string> g;
bool check(int sr, int sc, int gr, int gc, char x) {
	FOR(i, sr, gr + 1)
		FOR(j, sc, gc + 1)
		if (g[i][j] != x&&g[i][j] != '*')
			return false;
	return true;
}
void f(int sr, int sc, int gr, int gc) {
	FOR(i, sr, gr + 1)
		FOR(j, sc, gc + 1)
		g[i][j] = '*';
}
typedef pair<int, int> P;
typedef pair<P, P> PP;
int main() {
	int N;
	cin >> N;
	REP(_, N) {
		int R, C;
		cin >> R >> C;
		vector<string> in(R);
		REP(i, R)cin >> in[i];
		g = in;
		map<int, PP> memo;
		REP(i, R)REP(j, C)
			if (in[i][j] != '.')memo[in[i][j]] = PP(P(100, 100), P(0, 0));
		REP(i, R)REP(j, C)
			if (in[i][j] != '.') {
				chmin(memo[in[i][j]].SR, i);
				chmax(memo[in[i][j]].GR, i);
				chmin(memo[in[i][j]].SC, j);
				chmax(memo[in[i][j]].GC, j);
			}
		bool update = true;
		while (update) {
			update = false;
			string s;
			for (auto&it : memo) {
				//cout << it.second.SR<<" "<< it.second.SC<< " " << it.second.GR<< " " << it.second.GC << endl;
				if (check(it.second.SR, it.second.SC, it.second.GR, it.second.GC, it.first)) {
					f(it.second.SR, it.second.SC, it.second.GR, it.second.GC);
					s.push_back(it.first);
				}
			}
			update = s.size() > 0;
			for (auto &c : s) {
				//cout << c << endl;
				memo.erase(c);

			}
		}
		if (memo.size())cout << "SUSPICIOUS" << endl;
		else cout << "SAFE" << endl;


	}



}

Measured memory_bytes: 3068
#include<bits/stdc++.h>
#define ll long long int
#define mod 1000000007
using namespace std;




int main(){
	int n,i,j;
	cin>>n;
	int a[n][3];
	for(i=0;i<n;i++)
	{
		for(j=0;j<3;j++)
		cin>>a[i][j];
	}
	int dp[n+1][3];
	memset(dp,0,sizeof(dp));
	dp[1][0]=a[0][0];
	dp[1][1]=a[0][1];
	dp[1][2]=a[0][2];
	for(i=2;i<=n;i++)
	{
		for(j=0;j<3;j++)
		{
			if(j==0)
			dp[i][j]=a[i-1][j]+max(dp[i-1][1],dp[i-1][2]);
			if(j==1)
			dp[i][j]=a[i-1][j]+max(dp[i-1][0],dp[i-1][2]);
			if(j==2)
			dp[i][j]=a[i-1][j]+max(dp[i-1][0],dp[i-1][1]);
		}
	}
	int ans=0;
	for(i=0;i<3;i++)
	ans=max(ans,dp[n][i]);
	cout<<ans;
	
	
	
}

Measured memory_bytes: 2560
import java.util.*;
public class Main{
	public static void main(String[] args)
	{
		Scanner sc=new Scanner(System.in);
		long n=sc.nextLong();
		long p=1000;
		if(n%1000==0)
		{
			System.out.println("0");
		    return;
		}
		else
		{
		for(int i=0;i<100000;i++)
		{
			if(p>n)
			{
				System.out.println(p-n);
				break;
			}
			else
			{
				p=p+1000;
			}
		}
		}
	}

}


Measured memory_bytes: 35672
#include <bits/stdc++.h>
using namespace std;
#define repr(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define reprrev(i,a,b) for(int i=b-1;i>=a;i--) // [a, b)
#define reprev(i,n) reprrev(i,0,n)
typedef long long ll;
typedef unsigned long long ull;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
    sizeは(int)とキャストしよう
    cin.tie(0);
    ios::sync_with_stdio(false);<- これら、printfとかと併用しない方が良さそう

*/

const ll mod = 1e9+7;

void chmod(ll &M){
    if(M >= mod) M %= mod;
    else if(M < 0){
        M += (abs(M)/mod + 1)*mod;
        M %= mod;
    }
}

ll modpow(ll x, ll n){
    if(n==0) return 1;
    ll res=modpow(x, n/2);

    if(n%2==0) return res*res%mod;
    else return res*res%mod*x%mod;
}

int getl(int i, int N) { return i==0? N-1:i-1; };
int getr(int i, int N) { return i==N-1? 0:i+1; };


// 線分 ab の偏角 返り値は[-π, π]
double argument(const pair<double, double> &a, const pair<double, double> &b){
    double ax=a.first, ay=a.second, bx=b.first, by=b.second;
    return atan2(by-ay, bx-ax);
}

/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */


class UnionFind{
public:
    //親の番号を格納する。親だった場合はー（その集合のサイズ）
    vector<int> parents;
    int count;

    //作る時はparentsを-1で初期化する
    //こうすることで全部ばらばらになる
    UnionFind(int n){
        parents = vector<int>(n, -1);
        count = n;
    }

    //Aがどのグループにいるか調べる
    int root(int A){
        if(parents[A]<0) return A;
        return parents[A] = root(parents[A]);
    }

    //自分のいるグループの大きさを調べる
    int size(int A){
        return -parents[root(A)];
    }

    //AとBをくっつける
    bool connect(int A, int B){
        //AとBを直接ではなく親同士をくっつける
        A=root(A);
        B=root(B);
        if(A==B){
            return false;
        }

        //大きい方（A)に小さい方（B)をくっつけたい
        if(size(A)<size(B)) swap(A, B);

        parents[A] += parents[B];
        parents[B] = A;
        --count;

        return true;
    }
};

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

    int N, K, L; cin >> N >> K >> L;
    UnionFind rails(N), roads(N);

    rep(i, K){
        int p, q; cin >> p >> q; --p; --q;
        roads.connect(p, q);
    }
    rep(i, L){
        int r, s; cin >> r >> s; --r; --s;
        rails.connect(r, s);
    }

    map<pair<int, int>, int> mp;
    rep(i, N) mp[make_pair(rails.root(i), roads.root(i))]++;

    rep(i, N) {
        if(i) cout << ' ';
        cout << mp[make_pair(rails.root(i), roads.root(i))];
    }
    cout << endl;
    
    return 0;
}

Measured memory_bytes: 13568
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
 ll N,x; cin >> N >> x;
  vector<ll> A(N);
 for(ll i = 0; i < N; i++){ cin >> A[i];}
  sort(A.begin(),A.end());
  
  int cnt = 0;
  for(int i = 0; i < N; i++){
    if( i == N-1){
      if( x == A[N-1]){ cnt++;} break;}
    if( x >= A[i]){ x -= A[i]; cnt++;}
    else{ break;}
  }
  
  cout << cnt << endl; return 0;}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <iomanip>
#include <set>
#include <map>
#include <climits>
#include <utility>
#include <deque>
#include <list>
#include <stdexcept>
using namespace std;

#define ll long long
#define VEC2(type, name, dim0, dim1, init_val) vector<vector<type>> name(dim0, vector<type>(dim1, init_val))
#define IN(type, name) type name; cin >> name
#define IN_V(type, name, size) vector<type> name(size); for(auto& x: name) cin >> x
#define IN_VPair(type1, type2, name, size) vector<pair<type1, type2>> name(size); for(auto& x: name) cin >> x.first >> x.second
#define IN_VW(type, name, size) vector<type> name(size); for(auto& x: name)

#define REP(name, start, end) for(ll name = (start); (name) < (end); ++(name))
#define REPR(name, end, start) for(ll name = (start - 1); (name) >= (end); --(name))
#define ALL(iterable) (iterable).begin(), (iterable).end()

template<typename _T> void OutIter(_T beg, _T end, string separator = " ", bool eol = true) {
	cout << *beg;
	for (auto it = beg + 1; it != end; ++it) {
		cout << separator << *it;
	}
	if(eol)cout << endl;
}

int main()
{
	cout << fixed << setprecision(6);
	IN(ll, n);

	cout << (n * (n - 1)) / 2 << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//------------------------------------------------------------------------------
//------------------------------------------------------------------------------
void _main()
{
    int N;
    cin >> N;

    vector<ll> A(N + 1), B(N);
    rep(i, 0, N + 1) cin >> A[i];
    rep(i, 0, N) cin >> B[i];

    ll ans = 0;

    rep(i, 0, N)
    {
        {
            const ll beatNum = min(B[i], A[i]);
            B[i] -= beatNum;
            A[i] -= beatNum;
            ans += beatNum;
        }
        {
            const ll beatNum = min(B[i], A[i + 1]);
            B[i] -= beatNum;
            A[i + 1] -= beatNum;
            ans += beatNum;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> iint;
typedef pair<ll,ll> llll;
#define ALL(x) (x).begin(),(x).end()
const ll zero = 0;
const ll INF = 3000000000000000000; //10^18
const int inINF = 1000000000; //10^9
const ll MOD = 1000000007; //10^9+7
const ll MOD2 = 998244353;

int main(){
    int N;
    cin >> N;
    vector<ll> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    ll m = 0;
    int J;
    for (int i = 0; i < N; i++) {
        if(m < abs(A[i])){
            m = abs(A[i]);
            J = i;
        }
    }

    if(m == 0){
        printf("0\n");
        return 0;
    }
    printf("%d\n", 2*N-1);
    for (int i = 0; i < N; i++) {
        printf("%d %d\n", J+1, i+1);
    }
    if(A[J] > 0){
        for (int i = 0; i < N-1; i++) {
            printf("%d %d\n", i+1, i+2);
        }
    }
    else{
        for (int i = N-2; i >= 0; i--) {
            printf("%d %d\n", i+2, i+1);
        }        
    }




}

Measured memory_bytes: 3668
from heapq import heapify, heappop, heappush
N, M = map(int, input().split())
A = [-a for a in list(map(int, input().split()))]
heapify(A)
for _ in range(M):
  p = heappop(A)
  heappush(A, -((-p)//2))
print(-sum(A))

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

int main(){
    int n;cin>>n;
    vin a(n);rep(i,n)cin>>a[i];
    sort(all(a),greater<int>());
    int tmp=a[0];
    ll l=0;
    rep2(i,1,n){
        if(a[i]==tmp){
            if(l==0){
                l=(ll)a[i];
                tmp=0;
            }
            else{
                cout<<l*(ll)a[i]<<endl;
                return 0;
            }
        }
        else tmp=a[i];
    }
    cout<<0<<endl;
}

Measured memory_bytes: 640