akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
//using Graph = vector<vector<int>>;
using P = pair<int,pair<int,int>>;
//int dy[4] = {-1,0,1,0};
//int dx[4] = {0,-1,0,1};

/*
void dfs(vector<vector<P>> &data,vector<pair<int,int>> &m,vector<int> &ans,int i,int money)
{
    
    
    
    
}

int main()
{
    int N,M,S;
    cin >> N>>M>>S;
    
    vector<vector<P>> data(N); //basyo,money,time;
    
    for(int i=0;i<M;i++)
    {
        int a,b,c,d;
        cin >> a >> b >> c >> d;
        a--;
        b--;
        
        data[a].push_back(make_pair(b,make_pair(c,d)));
        data[b].push_back(make_pair(a,make_pair(c,d)));
    }
    
    vector<pair<int,int>> m(N);
    for(int i=0;i<N;i++)
    {
        cin >> m[i].first >> m[i].second;
    }
    
    vector<int> ans(N,INT_MAX);
    ans[0] = 0;
    dfs(data,m,ans,0,S);
    
    
    
    return 0;
}
*/

int main()
{
    string S;
    cin >> S;
    
    int N = (int)S.size();
    vector<int> data(N);
    
    int temp = 0;
    int temp2 = 1;
    long long ans = 0;
    data[N-1] = S[N-1] - '0';
    temp = data[N-1];
    for(int i=0;i<N-1;i++)
    {
        temp2 = (temp2 * 10) %2019;
        temp +=(S[N-2 - i] - '0') * temp2;
        temp %= 2019;
        
        data[N-2-i] = temp;
    }
    
    sort(data.begin(),data.end());
    
    int temp3 = 0;
    long long count = 0;
    for(int i=0;i<N;i++)
    {
        if(data[i] == temp3)
        {
            count ++;
        }
        else
        {
            temp3 = data[i];
            ans += (count)  * (count+1) /2;
            count = 0;
        }
    }
    ans += (count)  * (count+1) /2;

    
    
    /*
    cout << 8 << endl;
    cout << 18 << endl;
    cout << 718 << endl;
    cout << 1718 << endl;
    cout << 81718%2019 << endl;
    cout << 181718%2019 << endl;
    cout << 3181718%2019 << endl;
    */
    cout << ans << endl;
    
    
    
    
    
    return 0;
}

/*
int main()
{
    int N;
    cin >> N;
 
    return 0;
}
*/
/*
 if(ok) cout << "Yes" << endl;
 else cout << "No" << endl;
 */


/*
    int N;
    cin >> N;
    
    int ans;
    cout >> ans;
    */

Measured memory_bytes: 4316
"use strict";
var input=require("fs").readFileSync("/dev/stdin","utf8");
var cin=input.split(/ |\n/),cid=0;
function next(a){return a?cin[cid++]:+cin[cid++];}
function nexts(n,a){return a?cin.slice(cid,cid+=n):cin.slice(cid,cid+=n).map(a=>+a);}
function nextm(h,w,a){var r=[],i=0;if(a)for(;i<h;i++)r.push(cin.slice(cid,cid+=w));else for(;i<h;i++)r.push(cin.slice(cid,cid+=w).map(a=>+a));return r;}
function xArray(v){var a=arguments,l=a.length,r="Array(a["+--l+"]).fill().map(x=>{return "+v+";})";while(--l)r="Array(a["+l+"]).fill().map(x=>"+r+")";return eval(r);}

var myOut = main();
if(myOut !== undefined)console.log(myOut);

function main(){
  var n = next(), k = next();
  var ans = 0;
  while(n){
    ans++;
    n = n/k|0;
  }
  return ans;
}

Measured memory_bytes: 7500
#include <bits/stdc++.h>
using namespace std;
#define forn(i, x, n) for (int i = x; i < n; i++)
#define all(a) (a).begin(), (a).end()
#define pii pair<int, int>
#define pll pair<ll, ll>
typedef long double ld;
typedef long long ll;
template <typename... Args> void dbg(Args &&... args) {
  using expander = int[];
  (void)expander{
      0,
      (static_cast<void>(void(cout << std::forward<Args>(args) << " ")), 0)...};
  cout << endl;
}
void gen() {
  exit(0);
}

int n, k;

void input() {
  scanf("%d %d", &n, &k);
}

void solve() {
  int x = n - (n / 2);

  if (x >= k) {
    printf("YES\n");
  } else {
    printf("NO\n");
  }
}

void clean() {
  scanf(" ");
}

int main() {
#ifdef DEBUG
  freopen("input", "r", stdin);
  // freopen("output", "w", stdout);
  // gen();
  while (!feof(stdin)) {
#endif
    input();
    solve();
#ifdef DEBUG
    clean();
  }
#endif
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
 #include <algorithm>
 #include <string>
 #include <set>
 using namespace std;
 int main() {
     int n;
     string s;
     cin >> n;
     for(int i=0; i<n; ++i) {
         cin >> s;
         set<string> A;
         A.insert(s);
         for(size_t j=1; j<s.size(); ++j){
             string l = s.substr(0,j);
             string r = s.substr(j);
             reverse(l.begin(),l.end());
             reverse(r.begin(), r.end());
             string l2 = l;
             string r2 = r;
             reverse(l.begin(),l.end());
             reverse(r.begin(), r.end());
             A.insert(l+r2);
             A.insert(l2+r);
             A.insert(l2+r2);
             A.insert(r+l);
             A.insert(r+l2);
             A.insert(r2+l);
             A.insert(r2+l2);
         }
         cout << A.size() << endl;
     }
     return 0;
 }


Measured memory_bytes: 3164
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {

		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		
		int nnn = 0;
		int ans = 0;
		for (int i = 1; i <= 9; i++) {
			nnn = i + (i * 10) + (i* 100); 
			if(n <= nnn) {
				ans = nnn; 
				break;
			}
		}
		System.out.println(nnn);
		
	}
}

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

void solve(){

	int n ;
	cin>>n ;

	unordered_map<int,int> mp ;

	int count=1 ;

	while(true){

		//cout<<n<<" "<<count<<"\n" ;
		
		if(mp[n]==1){
			break ;
		}
		mp[n]=1 ;

		if(n%2==0){
			n=n/2 ;
		}
		else{
			n=3*n+1 ;
		}

		count++ ;

	}

	cout<<count ;
}

int main(){

	int y ;

	y=1 ;
	//cin>>y ;

	while(y--)
	{	
		solve() ;
	}

}

Measured memory_bytes: 3636
#include <iostream>
using namespace std;
int main(void){
    int n;
    cin >> n;
    while(n != 0){
        int a[31] = {};
        a[1] = 1;
        a[2] = 2;
        a[3] = 4;
        for(int i = 4; i < 31; i++){
            a[i] = a[i-1] + a[i-2] + a[i-3];
        }
        cout << ((a[n]/10)/365)+1 << endl;
        cin >> n;
    }
}


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

int main(){
	long long int dif=LLONG_MAX,sum=0,sum_arai=0;
	int N;
	cin >> N;
	int a[N];
	for(int i=0;i<N;i++){
		cin >> a[i];
		sum_arai+=a[i];
	}
	sum+=a[0],sum_arai-=a[0];
	if(abs(sum-sum_arai)<dif){
		dif=abs(sum-sum_arai);
	}
	for(int i=1;i<N-1;i++){
		sum+=a[i];
		sum_arai-=a[i];
		if(abs(sum-sum_arai)<dif){
			dif=abs(sum-sum_arai);
		}
	}
	cout << dif << endl;
	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define countof(array) (sizeof(array) / sizeof(array[0]))
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = (n)-1; i >= 0; --i)
#define rep2(i,n) for(int i = 1; i <= (n); ++i)
#define rrep2(i,n) for(int i = (n); i > 0; --i)
#define srep(i,s,n) for(int i = s; i < (n); ++i)
#define rsrep(i,s,n) for(int i = (n)-1; i >= s; --i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define aall(a) (a), (a)+countof(a)//for array sorting
#define raall(a) (a), (a)+countof(a), greater<>()
#define show(x) cout<<#x<<" = "<<(x)<<endl;
#define vfind(v, a) find(all(v), a) != v.end()
#define yn(f) { if (f) puts("YES"); else puts("NO"); }
#define yns(f) { if (f) puts("Yes"); else puts("No"); }
#define show_ary(...) { cout<<#__VA_ARGS__<<" = "; for (const auto& x : (__VA_ARGS__)) { cout<<x<<" "; } cout<<endl; }
#define show_pair(...) cout<<#__VA_ARGS__<<" = "<<endl; for (const auto& x : (__VA_ARGS__)) { cout<<"  "<<x.fi<<" : "<<x.se<<endl; }
#define out_ary(...) { int n = (__VA_ARGS__).size(); rep(i, n) printf("%d%s", (__VA_ARGS__)[i], i != n-1 ? " " : "\n"); }
#define argmax(v) distance((v).begin(), max_element(all(v)))
#define argmin(v) distance((v).begin(), min_element(all(v)))
#define vmax(v) *max_element(all(v))
#define vmin(v) *min_element(all(v))
typedef long long int ll;
typedef pair<int, int> P;
typedef vector<P> vpair;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<double> vdouble;
typedef vector<string> vstr;
typedef vector<bool> vbool;
typedef vector<vint> vvint;
typedef vector<vll> vvll;
typedef vector<vstr> vvstr;
typedef vector<vbool> vvbool;
const ll LINF = 2000000000000000000ll;
const int INF = 1000000100;
const ll MOD = 1e9+7;


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

    int ans = 0;
    rep(i, 1000) {
        string p = to_string(i);
        while(p.length() < 3) {
            p = '0'+p;
        }
        string tmp = s;
        bool check = true;
        int id = -1;
        rep(j, 3) {
            int pre = id;
            id = -1;    
            srep(k, pre, n) {
                if (tmp[k] == p[j]) {
                    tmp[k] = '*';
                    id = k;
                    break;
                }
            }
            if (id == -1) check = false;
        }
        if (check) ans++;

    }

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

Measured memory_bytes: 384
fn main() {
    let (n, m) = {
        let mut s = String::new();
        std::io::stdin().read_line(&mut s).unwrap();
        let mut ws = s.trim_right().split_whitespace();
        let n: i32 = ws.next().unwrap().parse().unwrap();
        let m: i32 = ws.next().unwrap().parse().unwrap();
        (n, m)
    };

    if n > 9 || m > 9 {
        println!("{}", -1);
    } else {
        println!("{}", n*m);
    }
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>
#include <iostream>
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
 
 
using namespace __gnu_pbds;
using namespace std;
 
 
typedef tree<int, null_type, less<int>, rb_tree_tag,
            tree_order_statistics_node_update>
    ordered_set;
 
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef double ld;
typedef unsigned long long ui64;
 
template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }
const int mod=1000000007;
  i64 poww(i64 a, i64 b)
  {
    a%=mod;
    i64 res=1;
    while(b)
      {
if(b&1)res=res*a%mod;
 
      a=a*a%mod;
      b/=2;
 
      }
      return res;
  }
  i64 inv(i64 a)
  {
    return poww(a,mod-2);
  }
 
 
  int main()
  {
ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    // ifstream fin(".in");
    // ofstream fout(".in");
 
 
i64 w,s;
cin>>s>>w;
if(w>=s)cout<<"unsafe";
else cout<<"safe";
 
    return 0;
  }

Measured memory_bytes: 3640
program balance

 implicit none
 integer::n,answer,i,j,k
 integer,allocatable::w(:),s1(:),s2(:),ans(:)

 read*,n
 allocate(w(n),s1(n),s2(n),ans(n))
 read*,w
 
 s1=0
 s2=0
 do i=1,n
  do j=1,i
   s1(i)=s1(i)+w(j)
  end do
  do k=n,i+1,-1
   s2(i)=s2(i)+w(k)
  end do
   ans(i)=abs(s1(i)-s2(i))
 end do

 answer=minval(ans)
 print*,answer

end program balance

Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
#define MAXN 300000
#define rint register int
inline int read(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}
int pre[MAXN+5], suf[MAXN+5]; char s[MAXN+5]; int n, Ans = MAXN+5;
int main()
{
	n = read(); scanf("%s",s+1); for(rint i = 1; i <= n; pre[i] = pre[i-1]+(s[i]=='W'), i++);
	for(rint i = n; i; suf[i] = suf[i+1]+(s[i]=='E'), i--); for(rint i = 1; i <= n; Ans = min(Ans,pre[i-1]+suf[i+1]), i++);
	cout << Ans << endl; return 0;
}

Measured memory_bytes: 2944
#include <algorithm>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = long long;
#define fst first
#define snd second

/* clang-format off */
template <class T, size_t D> struct _vec { using type = vector<typename _vec<T, D - 1>::type>; };
template <class T> struct _vec<T, 1> { using type = vector<T>; };
template <class T, size_t D> using vec = typename _vec<T, D>::type;
template <class T> vector<T> make_v(size_t size, const T& init) { return vector<T>(size, init); }
template <class... Ts> auto make_v(size_t size, Ts... rest) { return vector<decltype(make_v(rest...))>(size, make_v(rest...)); }
/* clang-format on */

const ll MOD = 1e9 + 7;

int main() {
  const string T = "ABC", G = "ABC";
  string S;
  while (cin >> S) {
    int N = S.size(), M = T.size(), L = G.size();
    vector<ll> coef(M, 0);
    for (int j = 0; j < M; j++) {
      for (int k = 0; k < L; k++) {
        if (G[k] == T[j]) {
          ++coef[j];
        }
      }
    }
    vec<ll, 2> dp = make_v(N + 1, M + 1, 0ll);
    dp[0][0] = 1;
    for (int i = 0; i < N; i++) {
      if (S[i] != '?') {
        for (int j = 0; j <= M; j++) {
          dp[i + 1][j] = dp[i][j];
        }
        for (int j = 0; j < M; j++) {
          if (S[i] == T[j]) {
            (dp[i + 1][j + 1] += dp[i][j]) %= MOD;
          }
        }
      } else {
        for (int j = 0; j <= M; j++) {
          dp[i + 1][j] = L * dp[i][j] % MOD;
        }
        for (int j = 0; j < M; j++) {
          (dp[i + 1][j + 1] += coef[j] * dp[i][j] % MOD) %= MOD;
        }
      }
    }
    cout << dp[N][M] << endl;
  }
  return 0;
}


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

int main () {
  long long N;
  cin >> N;
  long long attack = 1;
  long long ans = 0;
  while (true){
    N /= 2;
    ans += attack;
    attack *= 2;
    if (N == 0) break;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
 
using namespace std;
 
int numcnt1[100000] = {};
int numcnt2[100000] = {};
 
int main(){
	int n;
	bool flg = false;
	cin >> n;
	for(int i=0;i<n;++i){
		int val;
		scanf("%d",&val);
		if(flg){
			--numcnt1[val];
		}else{
			--numcnt2[val];
		}
		flg ^= 1;
	}
	int *m1 = min_element(&numcnt1[0],&numcnt1[100000]);
	int *m2 = min_element(&numcnt2[0],&numcnt2[100000]);
	n = n / 2;
	if((m1 - numcnt1) == (m2 - numcnt2)){
		int m = n + *m1;
		numcnt1[m1 - numcnt1] = 999999;
		numcnt2[m2 - numcnt2] = 999999;
		int *mm1 = min_element(&numcnt1[0],&numcnt1[100000]);
		int *mm2 = min_element(&numcnt2[0],&numcnt2[100000]);
		if(*mm1 == 0 && *mm2 == 0){
			cout << n << endl;
		}else if(*mm1 < *mm2){
			cout << n + *mm1 + m << endl;
		}else{
			cout << n + *mm2 + m << endl;
		}
	}else{
		cout << n + *m1 + (n + *m2) << endl;
	}
}

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

#define INF 1e9
#define LLINF 1e18
#define PI 3.1415926535897932384
#define MOD 1000000007

#define REP(i, n) for(int i=0; i<n; ++i)
#define REPR(i, n) for(int i=n; i>=0; --i)
#define REPS(i, m, n) for(int i=m; i<n; ++i)
#define SORT(v, n) sort(v, v+n)
#define RSORT(v, n) sort(v, v+n, greater<int>());
#define VSORT(v) sort(v.begin(), v.end());
#define RVSORT(v) sort(v.rbegin(), v.rend());
#define PB(n) push_back(n)
using namespace std;

int main() {
  for(;;) {
    int n, m;
    cin >> n >> m;
    if(n == 0) return 0;

    vector<int> v(n);
    REP(i,n) 
      cin >> v[i];
    RVSORT(v);

    for(int i=m-1; i<n; i+=m)
      v[i] = 0;

    cout << accumulate(v.begin(), v.end(), 0) << endl;
  }
}






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

int main()
{
    int n,a[200],ans=0;
    scanf("%d",&n);n*=2;
    for (int i=0;i<n;i++)
        scanf("%d",&a[i]);

    sort(a,a+n);

    for (int i=0;i<n;i+=2)
        ans+=a[i];
    printf("%d",ans);

}


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

typedef long long ll;

int main()
{
    int q;

    cin >> q;

    for (int i = 0; i < q; ++i) {
        int c, a, n, ans = 0;
        cin >> c >> a >> n;

        while (c >= 1 && a >= 1 && n >= 1) {
            ans++;
            c--; a--; n--;
        }

        while (c >= 2 && a >= 1) {
            ans++;
            c -= 2; a--;
        }

        while (c >= 3) {
            ans++;
            c -= 3;
        }

        printf("%d\n", ans);
    }

    return 0;
}




Measured memory_bytes: 3196
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int n, q;
long long m;
int fa[N];
int Find(int x) {return fa[x] == x ? x : fa[x] = Find(fa[x]);}
void Union(int x, int y) {
	x = Find(x), y = Find(y);
	if (x != y) fa[x] = y;
}
int main() {
	scanf("%d%lld%d", &n, &m, &q);
	vector<pair<int, int> > vec;
	for (int i = 0; i < n; i++) fa[i] = i;
	while (q--) {
		int u, v, c;
		scanf("%d%d%d", &u, &v, &c);
		if (c == 0)
			Union(u, v);
		else
			vec.push_back(make_pair(u, v));
	}
	if (m == n - 1) {
		if (vec.size()) puts("No");
		else puts("Yes");
		return 0;
	}
	for (pair<int, int> p : vec) {
		if (Find(p.first) == Find(p.second)) {
			puts("No");
			return 0;
		}
	}
	int cnt = 0;
	for (int i = 0; i < n; i++) if (fa[i] == i) cnt++;
	if (m > n - cnt + 1ll * (cnt - 1) * cnt / 2) puts("No");
	else puts("Yes");
	return 0;
}

Measured memory_bytes: 1784
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using mii = map<int, int>;
const int INF = 1e9;
const ll LINF = 1e18;
#define MP(a,b) make_pair((a),(b))
#define MT(...) make_tuple(__VA_ARGS__)

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define REPS(i,x) for(int i=1;i<=(int)(x);i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RREPS(i,x) for(int i=((int)(x));i>0;i--)

#define ALL(x) (x).begin(),(x).end()
#define IN(type,a) type a;cin >> a
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define COUT(x) cout << (x) << endl
#define DCOUT(x,n) cout << fixed << setprecision(n) << (x) << endl
int gcd(int x, int y){
    if ((x==1)||(y==1)) {
        return 1;
    }
    if (x>y) {
        if (x%y==0) {
            return y;
        }else{
            return gcd(y, x%y);
        }
    }else{
        if (y%x==0) {
            return x;
        }else{
            return gcd(x, y%x);
        }
    }
}
int main() {
    IN(int, n);
    int sum = 0;
    REPS(i, n){
        REPS(j, n){
            REPS(k, n){
                sum += gcd(i, gcd(j, k));
            }
        }
    }
    COUT(sum);
}




Measured memory_bytes: 3572
#include<stdio.h>
int main()
{
    int n, k, arr[105], i;
    scanf("%d%d", &n, &k);
    for(i = 1; i <= n; i++)scanf("%d", &arr[i]);
    int sum=0;
    for(i = 1; i <= n; i++)
    {
        int disA, disB;
        disA = arr[i];
        if(arr[i] >= k) disB = arr[i] - k;
        else disB =  k - arr[i];
        if(disA <= disB) sum = sum + 2*disA;
        else sum = sum + 2*disB;
    }
    printf("%d\n", sum);

}


Measured memory_bytes: 128
#include <algorithm> // max
 #include <iostream>
 using namespace std;
 int main(){
 int N;
 cin >> N;
 int S = 0, M = 0;
 for(int i = 0; i < N; ++i){ // ここでは商品番号を 0, 1, ..., N-1 とする
 int p;
 cin >> p;
 S += p;
 M = max(M, p); // M と p のうち大きい方。かなり便利! ちなみに小さい方は min
 }
 int ans = S - M / 2;
 cout << ans << endl;
 }

Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <vector>
#define debug(...) fprintf(stderr, __VA_ARGS__)

typedef long long ll;
typedef std::pair<ll, ll> mp;

struct {
	inline operator int () { int x; return scanf("%d", &x), x; }
	inline operator ll () { ll x; return scanf("%lld", &x), x; }
	template<class T> inline void operator () (T &x) { x = *this; }
	template<class T, class ...A> inline void operator () (T &x, A &...a)
	{ x = *this; this -> operator ()(a...); }
} read;

const int maxk = 100, mod = 1000000007;
ll fib[maxk], res; int mx;
std::vector<mp> excellent[maxk];

int main() {
	int k = 1;
	fib[0] = fib[1] = 1;
	ll lim = 1000000000000000000;
	while(fib[k] + fib[k - 1] <= lim) {
		++ k;
		fib[k] = fib[k - 1] + fib[k - 2];
	}

	excellent[1].push_back(mp(1, 2));
	for(int i = 2; i <= k; i ++) {
		for(mp p : excellent[i - 1])
			excellent[i].push_back(mp(p.second, p.first + p.second));
		excellent[i].push_back(mp(fib[i + 1], fib[i + 1] + fib[i - 1]));
	}

	int q = read;
	while(q --) {
		ll x = read, y = read;
		if(x > y) std::swap(x, y);

		mx = 1;
		while(mx + 2 <= k and fib[mx + 1] <= x and fib[mx + 2] <= y)
			++ mx;

		res = 0;
		for(mp p : excellent[mx]) {
			if(p.first <= x and p.second <= y)
				res += (y - p.second) / p.first + 1;
			if(p.second <= x)
				res += (x - p.second) / p.first + 1;
			res %= mod;
		}

		if(mx == 1)
			res += x;

		printf("%d %lld\n", mx, res);
	}
}

Measured memory_bytes: 4380
n,m,*a=map(int,open(0).read().split())
d=[0]*-~n
for i in range(1,n+1):
 for j,k in zip((1,2,3,4,5,6,7,8,9),(2,5,5,4,5,6,3,7,6)):
  if i-k>=0and(i-k<1or d[i-k])and j in a:d[i]=max(d[i],d[i-k]*10+j)
print(d[n])

Measured memory_bytes: 14388
import itertools
n,m=map(int,input().split())
edge=[[] for i in range(n+1)]
for i in range(m):
  a,b=map(int,input().split())
  edge[a].append(b)
  edge[b].append(a)
ans=0
for junretu in list(itertools.permutations(list(range(2,n+1)))):
  now=1
  flag=True
  for i in list(junretu):
    if not(i in edge[now]):
      flag=False
      break
    now=i
  if flag:
    ans+=1
print(ans)  

Measured memory_bytes: 9384
#include<bits/stdc++.h>
using namespace std;
vector<pair<int, int>> vp;
double calc(int i, int j) {
  int dx = abs(vp[i].first - vp[j].first);
  int dy = abs(vp[i].second - vp[j].second);
  return sqrt(dx * dx + dy * dy);
}
int main() {
  int N;
  cin >> N;
  vp.resize(N);
  for (auto& p : vp) cin >> p.first >> p.second;
  sort(vp.begin(), vp.end());

  vector<double> ans;
  do {
    double t = 0;
    for (int i = 1; i < N; i++) {
      t += calc(i - 1, i);
    }
    ans.push_back(t);
  } while (next_permutation(vp.begin(), vp.end()));
  
  double sum = 0;
  for (auto& x : ans) sum += x;
  cout << fixed << setprecision(12) << sum / ans.size() << endl;
}


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

int main(){

  ll q,h,s,d,n;
  cin>>q>>h>>s>>d>>n;
  h = min(q*2,h);
  s = min(h*2,s);
  d = min(s*2,d);
  ll ans;
  if(n%2==1){
    ans = n/2*d + s;
  }else{
	ans = n/2*d;
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>

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

#ifdef DEBUG
    #define IFD if(true)
#else
    #define IFD if(false)
#endif

int main()
{
    int N, K;
    string S;
    cin >> N >> K;
    cin >> S;

    int ans = 0;
    int sw = 0;
    rep(i, N) {
        if(i > 0 && S[i] == 'L' && S[i - 1] == 'L') {
            ans++;
        } else if(i < N - 1 && S[i] == 'R' && S[i + 1] == 'R') {
            ans++;
        }
        if(i < N - 1 && S[i] != S[i + 1]) {
            sw++;
        }
    }
    cout << ans + min(K * 2, sw) << endl;

    return 0;
}


Measured memory_bytes: 512
// #define _GLIBCXX_DEBUG // for STL debug (optional)
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define int long long int
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
typedef pair<int, int> pii;
typedef long long ll;
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const ll INF = 1001001001001001LL;
const ll MOD = 1000000007LL;
 
signed main() {
    int N, A, B; cin >> N >> A >> B;

    int cntA = 0, cntB = 0, cntC = 0;
    vector<int> P(N);
    for(int i=0; i<N; i++) {
        cin >> P[i];

        if(P[i] <= A) cntA++;
        else if(P[i] <= B) cntB++;
        else cntC++;
    }

    int ans = min({cntA, cntB, cntC});
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,k;
ll a[100005],dp[100005];
ll frog2(int idx)
{
    if(idx==n-1) return 0;
    if(idx>=n) return INT_MAX;
    ll &ans=dp[idx];
    if(ans!=-1)
        return ans;
    ans=INT_MAX;
    for(int i=1;i<=k;i++)
    {
        ll res=INT_MAX;
        if(idx+i<n)
            res=abs(a[idx]-a[idx+i]) + frog2(idx+i);
    
        ans=min(ans,res);
    }
    return ans;
}
int main()
{
    
    cin>>n>>k;
    memset(dp,-1,sizeof(dp));
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    cout<<frog2(0);
    return 0;
}

Measured memory_bytes: 6528
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define rep(i,n); for(long long i = 0;i < (n);i++)
using ll = long long;
using P = pair<long long,long long>;
template <class T> using vec = vector<T>;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s; cin >> s;
    cout << s[0] << s[1] << s[2] << endl; 
}

Measured memory_bytes: 3636
import sys
read = sys.stdin.buffer.read
#input = sys.stdin.readline
#input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode('utf-8')
from math import *


def main():
	n,c,k=MI()
	T=[II() for _ in range(n)]
	T.sort()
	#print(T)
	
	ans=0
	cnt=0
	now=0
	
	i=0
	
	while i<n:
		#print(i)
		now=T[i]
		ans+=1
		cnt=1
		while i<n and cnt<=c and now+k>=T[i]:
			i+=1
			cnt+=1
		cnt=0
	
	print(ans)
	
	
	
	
	


	
if __name__ == "__main__":
	main()


Measured memory_bytes: 13408
#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<int, int> ii;
const int INF = 1 << 29;
const int MOD = 1e9 + 7;

int main() {
  int x, y;
  cin >> x >> y;
  int ret = x - 1;
  if (y >= x) ret++;
  cout << ret << endl;
  return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Globalization;
using System.IO.Compression;
using System.IO.Pipes;
using System.Linq;
using System.Numerics;
using System.Text;
using static System.Console;
using static System.Math;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var ABCD = ReadInts();
            var A = ABCD[0];
            var B = ABCD[1];
            var C = ABCD[2];
            var D = ABCD[3];

            while (true)
            {
                C = C - B;
                if (C <= 0)
                {
                    WriteLine("Yes");
                    return;
                }
                A = A - D;
                if (A <= 0)
                {
                    WriteLine("No");
                    return;
                }
            }
        }

        private static string Read() { return ReadLine(); }
        private static string[] Reads() { return (Read().Split()); }
        private static int ReadInt() { return int.Parse(Read()); }
        private static long ReadLong() { return long.Parse(Read()); }
        private static double ReadDouble() { return double.Parse(Read()); }
        private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
        private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
        private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }
    }
}


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

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

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define D(x) cerr<<#x<<'='<<x<<'\n';
using namespace std;
typedef long long ll;
int cnt[200005];
string s[200005];
int main()
{
	int n;
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
		cin>>s[i];
	sort(s+1,s+1+n);
	int pre=0,mx=0;
	for (int i=1;i<=n;i++)
		if (s[i]==s[i-1])
			cnt[pre]++;
		else
		{
			mx=max(mx,cnt[pre]);
			cnt[pre=i]=1;
		}
	mx=max(mx,cnt[pre]);
	for (int i=1;i<=n;i++)
		if (cnt[i]==mx)
			cout<<s[i]<<endl;
	return 0;
}

Measured memory_bytes: 15104
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <queue>
#include <map>
 
using namespace std;
 
#define rep(i, n) for(int i = 0; i < (n); i++)
#define MP make_pair
#define X first
#define Y second
 
typedef pair<int, int> P;
 
int d[201][201];
 
const int INF = 1<<29;
int main(){
    int n;
    while(cin >> n, n){
        rep(i, 201) rep(j, 201) d[i][j] = INF;
        map<string, int> num;
        int idx = 0;
        bool ans = true;
        rep(i, n){
            string a, b;
            string c;
            cin >> c >> a >> c >> c >> b;
            if(!num[a]) num[a] = ++idx;
            if(!num[b]) num[b] = ++idx;
            int x = atoi(c.substr(3).c_str());
            // a = b+x
            int l = num[a], r = num[b];
            rep(k, 2){
                if(d[l][r] == INF){
                    d[l][r] = x;
                }else{
                    if(d[l][r] != x) ans = false;
                }
                swap(l, r);
                x = -x;
            }
            for(int j = 1; j <= idx; j++){
                for(int k = 1; k <= idx; k++){
                    if(d[k][j] == INF) continue;
                    for(int l = 1; l <= idx; l++){
                        if(d[j][l] == INF) continue;
                        d[k][l] = min(d[k][l], d[k][j]+d[j][l]);
                    }
                }
            }
        }
 
        cout << (ans?"Yes":"No") << endl;
    }
 
    return 0;
}

Measured memory_bytes: 1396
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <string.h>
const int N = 5e5+10;
#define ll long long
inline int read() {
	int r=0; char c=getchar();
	while (c<'0'||c>'9') c=getchar();
	while (c>='0'&&c<='9') r=r*10+c-'0', c=getchar();
	return r;
}
int a[N], sum;
int main() {
	int n = read();
	for (int i=1; i<=n; i++) a[i] = read(), sum ^= a[i];
	for (int i=1; i<=n; i++) printf("%d ", sum ^ a[i]); printf("\n");
}

Measured memory_bytes: 3308
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define dbg(...) do{cerr<<__LINE__<<": ";dbgprint(#__VA_ARGS__, __VA_ARGS__);}while(0);

using namespace std;

namespace std{template<class S,class T>struct hash<pair<S,T>>{size_t operator()(const pair<S,T>&p)const{return ((size_t)1e9+7)*hash<S>()(p.first)+hash<T>()(p.second);}};template<class T>struct hash<vector<T>>{size_t operator()(const vector<T> &v)const{size_t h=0;for(auto i : v)h=h*((size_t)1e9+7)+hash<T>()(i)+1;return h;}};}
template<class T>ostream& operator<<(ostream &os, const vector<T> &v){os<<"[ ";rep(i,v.size())os<<v[i]<<(i==v.size()-1?" ]":", ");return os;}template<class T>ostream& operator<<(ostream &os,const set<T> &v){os<<"{ "; for(const auto &i:v)os<<i<<", ";return os<<"}";}
template<class T,class U>ostream& operator<<(ostream &os,const map<T,U> &v){os<<"{";for(const auto &i:v)os<<" "<<i.first<<": "<<i.second<<",";return os<<"}";}template<class T,class U>ostream& operator<<(ostream &os,const pair<T,U> &p){return os<<"("<<p.first<<", "<<p.second<<")";}
void dbgprint(const string &fmt){cerr<<endl;}template<class H,class... T>void dbgprint(const string &fmt,const H &h,const T&... r){cerr<<fmt.substr(0,fmt.find(","))<<"= "<<h<<" ";dbgprint(fmt.substr(fmt.find(",")+1),r...);}
typedef long long ll;typedef vector<int> vi;typedef pair<int,int> pi;const int inf = (int)1e9;const double INF = 1e12, EPS = 1e-9;

int solve(int n, const vector<tuple<int,int,int>> &c1, const vector<tuple<int,int,int>> &c2){
	vector<vector<pi>> e(n);
	vi dist(n, inf);
	dist[0] = 0;
	
	rep(it, 2) for(auto i : (it ? c2 : c1)){
		int a, b, c; tie(a, b, c) = i;
		//s->t dist[t] <= dist[s] + c
		if(c > 0){
			e[b].emplace_back(a, -(c / 2)); //a + c <= b
		}
		else{
			e[b].emplace_back(a, 0); //a <= b
			e[a].emplace_back(b, abs(c) / 2); //b <= a + (-c)
		}
	}
	rep(it, n){
		bool up = 0;
		rep(i, n) for(auto j : e[i]) if(dist[j.first] > dist[i] + j.second){
			if(it == n - 1) return -1;
			up = 1;
			dist[j.first] = dist[i] + j.second;
		}
		if(!up) break;
	}
	if(*min_element(dist.begin() + 1, dist.end()) < 0) return -1;
	return *max_element(all(dist));
}

int main(){
	cin.tie(0); cin.sync_with_stdio(0);
	int n, m; cin >> n >> m;
	vector<tuple<int,int,int>> c1;
	vector<tuple<int,int,int>> c2;
	rep(i, m){
		string s; cin >> s;
		string t = s;
		rep(j, s.size()){
			if(isdigit(s[j])) t[j] = ' ';
			else s[j] = ' ';
		}
		stringstream ss(s), tt(t);
		int a, b, c; ss >> a >> b >> c; a--; b--;
		string op; char sig; tt >> op >> sig;
		
		c = c * 2 + 1;
		if(sig == '-') c *= -1;
		
		if(op == "*") c2.emplace_back(a, b, c);
		else{
			if(op == ">=") swap(a, b);
			c1.emplace_back(a, b, c);
		}
	}
	int ans = -1;
	rep(it, 1 << c2.size()){
		rep(i, c2.size()) if(it & 1 << i) swap(get<0>(c2[i]), get<1>(c2[i]));
		ans = max(ans, solve(n, c1, c2));
		rep(i, c2.size()) if(it & 1 << i) swap(get<0>(c2[i]), get<1>(c2[i]));
	}
	if(ans >= inf) cout << "inf" << endl;
	else cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3200
import java.util.*;

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

    int n = sc.nextInt();
    int k = sc.nextInt();
    String s = sc.next();

    char[] c = s.toCharArray();
    char target = c[k - 1];
    char replaced = Character.toLowerCase(target);

    StringBuilder sb = new StringBuilder(s);
    sb.setCharAt(k - 1, replaced);

    System.out.println(sb);
    
  }
}

Measured memory_bytes: 23764
import numpy as np
import itertools
if __name__ == "__main__":
    digit=int(input())
    values=[int(x) for x in input().split(' ')]
    cnt=0
    values_neighbor=['']*digit
    for i in range(0,len(values_neighbor)):
        values_neighbor[i] = (values[i]-1, values[i], values[i]+1)

    pare_list=list(itertools.product(*values_neighbor))

    pare=[np.array(x).prod() for x in pare_list]
    for x in pare:
        if x%2==0:
            cnt=cnt+1
    print(cnt)

Measured memory_bytes: 22364
#include <stdio.h>
#include <math.h>

int main(void) {
	double a, b, C;
	double PI = atan(1.0) * 4.0;
	double angle, h;
	if (scanf("%lf%lf%lf", &a, &b, &C) != 3) return 1;
	angle = C * PI / 180.0;
	h = b * sin(PI - angle);
	printf("%.15f\n", a * h / 2.0);
	printf("%.15f\n", a + b + sqrt(a*a + b*b - 2*a*b*cos(angle)));
	printf("%.15f\n", h);
	return 0;
}



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

inline int tax(int p, int x) {
  return (p * (100 + x)) / 100;
}

int solve(int x, int y, int s) {
  int mx = INT_MIN;
  for (int a = 1; a < s; ++a) {
    for (int b = 1; b < s; ++b) {
      auto s_ = tax(a, x) + tax(b, x);
      if (s_ < s) continue;
      else if (s_ == s) {
	mx = max(mx, tax(a, y) + tax(b, y));
      }
      else break;
    }
  }
  return mx;
}

int main() {
  int x, y, s;
  while(cin >> x >> y >> s, x | y | s)
    cout << solve(x, y, s) << endl;
  return 0;
}


Measured memory_bytes: 3012
# include <iostream>
# include <stack>
# include <iomanip>

using namespace std;

void call(int n) {
	int i = 1;
CHECK_NUM:
	int x = i;
	if (x % 3 == 0) {
		cout << " " << i;
		goto END_CHECK_NUM;
	}
INCLUDE3:
	if (x % 10 == 3) {
		cout << " " << i;
		goto END_CHECK_NUM;
	}
	x /= 10;
	if (x) goto INCLUDE3;
END_CHECK_NUM:
	if (++i <= n) goto CHECK_NUM;

	cout << endl;
}

int main() {
	int n;
	std::cin >> n;
	call(n);
	return 0;
}

Measured memory_bytes: 3092
#include<iostream>
using namespace std;
long long gcd(long long a, long long b){
	if (a < b)
		swap(a, b);
	if (b == 0)
		return a;
	return gcd(b, a%b);
}
int main(){
	long long n, m;
	cin >> n >> m;
	printf("%lld", n / gcd(n, m)*m);
	return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python3
import sys


def solve(A: int, B: int):
    ret = max(A + B, A * B, A - B)
    print(ret)


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    solve(A, B)

if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
int main(){
  int a[100000]={},n,x,b[100000]={};
  int j=0,cnt=1,ans=0;
  cin>>n;
  for(int i=0;i<n;i++)cin>>a[i];
  sort(a,a+n); 
  for(int i=1;i<=n;i++)
   if(a[i-1]!=a[i]){b[j]=cnt;j++;cnt=1;}
   else cnt++;
  j=0;
  ans=0;  
  for(int i=0;i<n;i++)
    if(a[i]!=a[i+1]){
      if(b[j]>=a[i]){ans+=b[j]-a[i];j++;}
      else {ans+=b[j];j++;}
    }
  cout<<ans<<endl;
  return 0;
}

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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,n,m) for(int i=(int)(n); i<=(int)(m); i++)
#define RFOR(i,n,m) for(int i=(int)(n); i>=(int)(m); i--)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

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 (a>b) { a=b; return 1; } return 0; }

#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define ins insert

using namespace std;

/* Some Libraries */

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

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n; cin>>n;
    vll a(n);
    rep(i,n) cin>>a[i];
    rep(i,n-1) a[i+1]+=a[i];
    ll mp=0,pm=0;
    ll diff=0;
    //-+-+
    rep(i,n){
        ll goal = (i&1)?1:-1;
        if (goal*(a[i]+diff)>0) continue;
        mp += abs(goal-(a[i]+diff));
        diff += goal-(a[i]+diff);
    }
    //+-+-
    diff=0;
    rep(i,n){
        ll goal = (i&1)?-1:1;
        if (goal*(a[i]+diff)>0) continue;
        pm += abs(goal-(a[i]+diff));
        diff += goal-(a[i]+diff);
    }
    cout<<min(mp,pm)<<"\n";
    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;

vector<vector <int> > stage;

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

int VISITED = 5;


void display(int w, int h){
  for(int i = 0; i < h; i++){
	for(int j = 0; j < w; j++){
	  cout << stage[i][j] << " ";
	}
	cout << endl;
  }
  cout << endl;
}

P getStart(int w, int h){
  bool start = false;
  P s;
  for(int i = 0; i < h; i++){
	for(int j = 0; j < w; j++){
	  if(stage[i][j] == 2){
		s.first = i;
		s.second = j;
		start = true;
		break;
	  }
	}
	if(start) break;
  }
  return s;
}



int dfs(int w, int h, int c, P s){
  int res = 100000;
  bool clearFlag = false;
  //display(w, h);
  if (c > 10) return res;
  
  for(int i = 0; i < 4; i++){
    int nx = dx[i] + s.second, ny = dy[i] + s.first;
    bool isRange = true;
	if(nx < 0 || nx >= w || ny < 0 || ny >= h || stage[ny][nx] == 1) continue;
    while(1){
      //cout << "nx = " << nx << " ny = " << ny << endl;
      
      if(nx < 0 || nx >= w || ny < 0 || ny >= h || stage[ny][nx] == 5){
        isRange = false;
        break;
      }
     
      if(stage[ny][nx] == 1){
        stage[ny][nx] = 0;
        break;
      }
      else if(stage[ny][nx] == 3){
        clearFlag = true;
        break;
      }
      nx += dx[i]; ny += dy[i];
	}
    //cout << "isRange = " << isRange << endl;
	int tmp = 0;
    if(isRange){
      if(clearFlag) return c;
      else {
		tmp = dfs(w, h, c + 1, P(ny - dy[i], nx - dx[i]));
		if(tmp < res) res = tmp;
		stage[ny][nx] = 1;
	  }
    }
  }
  
  return res;
}


int main(){
  int w, h;
  while(1){
	cin >> w >> h;
	if(w == 0 && h == 0) break;

    stage.resize(h);
	for(int i = 0; i < h; i++){
      stage[i].resize(w);
	  for(int j = 0; j < w; j++){
		cin >> stage[i][j];
	  }
	}
	
	P s = getStart(w, h);
    //cout << "sx = " << s.second << " sy = "  << s.first << endl;
	//display(w, h);
    int tmp = dfs(w, h, 1, s);
	if(tmp > 10) tmp = -1;
	cout << tmp << endl;
	
  }
  
  return 0;
}

Measured memory_bytes: 3148
#include <bits/stdc++.h>
#define maxn 300086

using namespace std;

int a[maxn];

inline void add(int x, int y){
	for(;x < maxn;x += x & -x) a[x] += y;
}

inline int query(int x){
	int sum = 0;
	for(;x;x -= x & -x) sum += a[x];
	return sum;
}

int n;
int p[maxn]; 

long long x, y;

int main(){
	scanf("%d", &n);
	for(int i = 1;i <= n;i++) scanf("%d", &p[i]);
	for(int i = 1;i <= n;i++) x += query(n) - query(p[i]), add(p[i], 1);
	memset(a, 0, sizeof(a));
	for(int i = 1;i <= n;i += 2) y += query(n) - query(p[i]), add(p[i], 1);
	memset(a, 0, sizeof(a));
	for(int i = 2;i <= n;i += 2) y += query(n) - query(p[i]), add(p[i], 1);
	printf(y * 3 == x ? "Yes" : "No");
}

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

int main( void ) {
    
    int n, m;
    cin >> n >> m;
    
    for( int j = 1; j <= m + 2; j ++ )
        cout << "#";
    cout << "\n";
    
    for( int i = 1; i <= n; i ++ ) {
        string str; cin >> str;
        cout << "#" << str << "#\n";
    }
    
    for( int j = 1; j <= m + 2; j ++ )
        cout << "#";
    cout << "\n";
    
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <limits.h>

#define MAX_NUM 101
#define MIN(a, b) ((a) < (b) ? (a) : (b))

void showM(int A[MAX_NUM][MAX_NUM], int n) {
	int i, j;

	for (i = 0; i <= n; ++i) {
		for (j = 0; j <= n; ++j) {
			printf("%d ", A[i][j]);
		}
		putchar('\n');
	}
}

int main(void) {
	int p[MAX_NUM] = {0};
	int m[MAX_NUM][MAX_NUM] ={0};
	int n, i, j, k, l, tmp;
	
	scanf("%d", &n);

	for (i = 0; i < 2 * n; ++i) {
		scanf(" %d", &p[(i+1)/2]);
	}

	for (l = 2; l <= n; l++) {
		for (i = 1; i <= n -l + 1; i++) {
//			showM(m, n);
			j = i + l - 1;
			m[i][j] = INT_MAX;
			for (k = i; k < j; ++k) {
//				printf("%d\n", m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j]);
				m[i][j] = MIN(m[i][j], m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j]);
			}
		}
	}

	printf("%d\n", m[1][n]);

	return 0;
}

Measured memory_bytes: 644
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int a,b,c,d,e;
    cin >> a >> b >> c >> d >> e;
    if (a==0){
        cout << '1' << endl;
    }else if (b==0){
        cout << '2' << endl;
    }else if (c==0){
        cout << '3' << endl;
    }else if (d==0){
        cout << '4' << endl;
    }else if (e==0){
        cout << '5' << endl;
    }
}

Measured memory_bytes: 3592
from bisect import bisect_right
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline


n, t = map(int, input().split())

shop = []
shop_a0 = []

for i in range(n):
    a, b = map(int, input().split())
    if a != 0:
        shop.append([a, b, a/(b+1)])
    else:
        shop_a0.append(b)

shop = sorted(shop, key=lambda x: -x[2])
shop_a0 = sorted(shop_a0)

n = len(shop)

INF = 10**10
dp = [[INF for _ in range(30)] for __ in range(n+1)]
dp[0][0] = 0

m = min(n+1, 30)

for i in range(n):
    for j in range(m):
        dp[i+1][j] = min(dp[i][j], dp[i][j-1] + 1 +
                         shop[i][0]*(dp[i][j-1]+1) + shop[i][1])
        dp[i+1][j-1] = min(dp[i+1][j-1], dp[i][j-1])

ss = []
if shop_a0:
    ss.append(1+shop_a0[0])
    for i in range(1, len(shop_a0)):
        ss.append(ss[-1]+1+shop_a0[i])

ans = 0

for i in range(m):
    if t - dp[n][i] >= 0:
        ans = max(ans, bisect_right(ss, t-dp[n][i]) + i)

print(ans)


Measured memory_bytes: 141652
/*
 * Author : Sadi
 * Sat 18/07/2020
 * 18:48:28.31
 */
#include <bits/stdc++.h>

using namespace std;

#define    watch(x); cout << "\n" <<  #x << " is: " << x << "\n";
#define    all(a) (a).begin(), (a).end()
#define    fi first
#define    se second

template<class A, class B>
ostream& operator << (ostream& output, const pair<A, B>& p) {
    output << "(" << p.first << ", " << p.second << ")";
    return output;
}

template<class A>
ostream& operator << (ostream& output, const vector<A>& a) {
    output << "[";
    for(auto it = a.begin(); it != a.end(); ++it) {
        if(it != a.begin()) {
            output << ", ";
        }
        output << *it;
    }
    output << "]";
    return output;
}

using lld = long long;
using pii = pair<int, int>;
using pll = pair<lld, lld>;

//const int inf = 1e9;
//const int mod = 1e9 + 7;
//const double PI = acos(-1.0);
//const int mx = 1e5 + 5;



int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#ifndef ONLINE_JUDGE
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
#endif // ONLINE_JUDGE

    int n, k;
    cin >> n >> k;
    deque<int> dq;
    for(int i = 0; i < n; ++i) {
        int h;
        cin >> h;
        dq.push_back(h);
    }
    // sort(dq.begin(), dq.end(), greater<int>());
    sort(dq.rbegin(), dq.rend());
    // for(int x:dq) {
    //     cout << x << " ";
    // }
    // cout << endl;
    long long moves = 0;
    for(int i = 0; i < k; ++i) {
        if(!dq.empty()) {
            dq.pop_front();
        }
        else {
            cout << 0 << "\n";
            return 0;
        }
    }
    for(int i = 0; i < (int) dq.size(); ++i) {
        moves += dq[i];
    }
    cout << moves << "\n";
    return 0;
}


Measured memory_bytes: 4020
#include<iostream>
#include<iomanip>
#include<cassert>
#include<math.h>
#include<complex>
#include<algorithm>
#include<utility>
#include<queue>
#include<string.h>
#include<string>
#include<set>
#include<map>
#include<unordered_map>
#include<functional>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
const ll INF=2e18;
const ll MOD=998244353;

const ll MAX = 1000000;
ll fac[MAX], finv[MAX], inv[MAX];
// nCk初期化
void nCkInit(const ll MOD) {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
ll nCk(ll n, ll k,const ll MOD){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
ll N,A,B,K;
int main(){
    cin>>N>>A>>B>>K;
    nCkInit(MOD);
    ll ans=0;
    for(ll aNum=0;aNum*A<=K && aNum<=N;aNum++){
        if((K-aNum*A)%B!=0)continue;
        ll bNum=(K-aNum*A)/B;
        if(aNum>N || bNum>N)continue;
        ans=(ans+nCk(N,aNum,MOD)*nCk(N,bNum,MOD)%MOD)%MOD;
    }
    cout<<ans;
    return 0;
}

Measured memory_bytes: 23680