akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Text;
using static System.Console;
using static System.Math;

namespace Atcoder
{
    class Program
    {
        static StreamWriter sw = new StreamWriter(OpenStandardOutput()) { AutoFlush = false };
        static void Main(string[] args)
        {
            try
            {
                SetOut(sw);
                Solve.Answer();
                Out.Flush();
            }
            catch (Exception ex)
            {
                WriteLine(ex.ToString());
            }
        }
    }

    public class Solve
    {
        public static void Answer()
        {
            var n = IO.RInt;
            var a = IO.RSInt;

            const int M = 1001001;
            var cnt = new int[M];
            Array.Sort(a);
            foreach (var x in a)
            {
                if (cnt[x] != 0)
                {
                    cnt[x] = 2;
                    continue;
                }
                for (int i = x; i < M; i += x)
                {
                    cnt[i]++;
                }
            }
            int ans = 0;
            foreach (var x in a)
            {
                if (cnt[x] == 1) ans++;
            }
            WriteLine(ans);
        }
    }

    public class IO
    {
        #region Input
        public static int RInt => int.Parse(ReadLine());
        public static long RLong => long.Parse(ReadLine());
        public static double RDouble => double.Parse(ReadLine());

        public static string[] RSString => ReadLine().Split();
        public static int[] RSInt => ReadLine().Split().Select(s => int.Parse(s)).ToArray();
        public static long[] RSLong => ReadLine().Split().Select(s => long.Parse(s)).ToArray();
        public static double[] RSDouble => ReadLine().Split().Select(s => double.Parse(s)).ToArray();
        #endregion

        #region Output
        public static void OutJoinSpace<T>(IEnumerable<T> list) => WriteLine(string.Join(" ", list));
        public static void WriteLineYes_or_No(bool flag) => WriteLine(flag ? "Yes" : "No");
        public static void WriteLineYES_or_NO(bool flag) => WriteLine(flag ? "YES" : "NO");
        #endregion
    }

    public class Mod
    {
        #region
        private readonly static long M = 1000000007;

        public static long Add(long a, long b) => (a * b) % M;
        public static long Sub(long a, long b) => (a - b) % M >= 0 ? (a - b) % M : (a - b) % M + M;
        public static long Multi(long a, long b) => (a * b) % M;
        #endregion
    }
}

Measured memory_bytes: 47204
#include <iostream>

int D[10004];

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

  int N;
  long long cnt = 0;
  cin >> N;
  for (int i = 0; i < N; ++i) {
    cin >> D[i];
  }
  for (int i = 0; i < N; ++i) {
    int x;
    cin >> x;
    x = D[i] - x;
    if (x < 0) cnt += (-x) / 2;
    else cnt -= x;
  }

  if (cnt >= 0) cout << "Yes" << '\n';
  else cout << "No" << '\n';
  return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;
using System.Threading.Tasks;

class Program
{
    void Run()
    {
        var sc = new Scanner();
        int n = sc.NextInt();
        int k = sc.NextInt();
        int[] a = new int[n];
        double[] p = new double[n];
        for (int i = 0; i < n; i++)
        {
            a[i] = sc.NextInt();
            p[i] = SeqSum(a[i]) / (double)a[i];
        }
        double sum = 0;
        for (int i = 0; i < k; i++)
        {
            sum += p[i];
        }
        double max = sum;
        for (int i = 0; i < n - k; i++)
        {
            sum -= p[i];
            sum += p[k + i];
            if (sum > max) max = sum;
        }
        Console.WriteLine(max);
    }

    int SeqSum(int n)
    {
        return n * (2 + (n - 1)) / 2;
    }

    static void Main(string[] args)
    {
        new Program().Run();
    }

    static long Gcd(long a, long b)

    {
        if (a < b) return Gcd(b, a);
        if (b == 0) return a;
        return Gcd(b, a % b);
    }

    static long Lcm(long a, long b)
    {
        long d = Gcd(a, b);
        return a / d * b;
    }

    static long RepeatedSquare(long n, long p, long m)
    {
        if (p == 0) return 1;
        if (p % 2 != 0) return n * RepeatedSquare(n, p - 1, m);
        long t = RepeatedSquare(n, p / 2, m);
        return (t * t) % m;
    }
}

class Scanner
{
    int index = -1;
    string[] buf;

    public Scanner()
    {
    }

    public int NextInt()
    {
        CheckNext();
        return int.Parse(buf[index++]);
    }

    public long NextLong()
    {
        CheckNext();
        return long.Parse(buf[index++]);
    }

    public double NextDouble()
    {
        CheckNext();
        return double.Parse(buf[index++]);
    }

    public string NextString()
    {
        CheckNext();
        return buf[index++];
    }

    private void CheckNext()
    {
        if (index >= 0 && index < buf.Length) return;

        buf = Console.ReadLine().Split(' ');
        index = 0;
    }
}


Measured memory_bytes: 31836
n=int(input())
poll={}
m=0
rtn=[]
for v in range(n):
    s=input()
    if s in poll:
        poll[s]+=1
        if poll[s]>m:
            m=poll[s]
    else:
        poll[s]=0
for s in poll:
    if poll[s]==m:
        rtn.append(s)
rtn.sort()
for x in rtn:
    print(x)
        
    


Measured memory_bytes: 32096
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,l,r) for(long long i=(l);i<(r);++i)
#define REP(i,n) FOR(i,0,n)
#define REPS(i,n) FOR(i,0,n+1)
#define int long long
#define mp make_pair
#define pb push_back
#define eb emplace_back
const int MOD=1e9+7;
const int INF=1e18;
 
signed main(){
    int N;cin>>N;
    map<int,int>Amemo;
    map<int,int>Bmemo;
    REP(i,N){
        int a;cin>>a;
        Amemo[a+i]++;
        Bmemo[a-i]++;
    }
    int ans=0;
    for(auto v:Amemo){
        int pls=Amemo[v.first]*Bmemo[-v.first];
        ans+=pls;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 37948
N, *A = map(int, open(0).read().split())

A = [0] + A
B = [0] * (N + 1)
sum_B = 0
for i in range(N, 0, -1):
    if sum(B[j] for j in range(i, N + 1, i)) % 2 != A[i]:
        B[i] = 1
        sum_B += 1
print(sum_B)
print(*[i for i, b in enumerate(B) if b])


Measured memory_bytes: 17512
/*
    -ensure correct output format
    -ensure printing required output
    -reread the problem statement
  */

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll>pll;
typedef pair<ll,pair<ll,ll>>plll;
#define fastread() (ios_base:: sync_with_stdio(false),cin.tie(NULL));
#define vll(v) v.begin(),v.end()
#define all(x) x.rbegin(),x.rend()
#define min3(a, b, c)   min(a, min(b, c))
#define max3(a, b, c)   max(a, max(b, c))
#define F first
#define S second
#define in  freopen("input.txt", "r", stdin)
#define out  freopen("output.txt", "w", stdout)
#define minheap int,vector<int>,greater<int>
#define pb push_back
#define eb emplace_back
#define ischar(x)  (('a' <= x && x <= 'z') || ('A' <= x && x <= 'Z'))
#define isvowel(ch) ((ch=='a'||ch=='e'||ch=='i'||ch=='o'||ch=='u')||(ch=='A'|| ch=='E' || ch=='I'|| ch=='O'|| ch=='U'))
#define bug cout<<"BUG"<<endl;
const int Max = 1e6 + 10;
const int Mod = 1e9 + 7;
const double PI  =3.141592653589793238463;
bool compare(const pair<ll,ll> &a, const pair<ll,ll> &b)
{
    return (a.first > b.first);
}
ll lcm(ll a,ll b)
{
    if(a==0 || b==0)return 0;

    return a/__gcd(a,b)*b;
}

void input(ll ara[],ll n)
{
    for(ll i=0; i<n; i++)cin>>ara[i];
}


vector<ll>adj[Max+10];
ll indeg[Max+10];

void addEdege(ll u,ll v)
{
    indeg[v]++;

    adj[u].eb(v);
}

ll cost[Max+10];

ll connect[Max+10];


ll topsort(ll s,ll last)
{


    queue<ll>q;

    q.push(s);

    cost[s]=1;

    ll u;

    while(!q.empty())
    {
        u=q.front();

        q.pop();

        for(auto v  : adj[u])
        {
            cost[v]=(cost[v]+cost[u])%Mod;

            indeg[v]--;

            if(!indeg[v])
                q.push(v);
        }
    }


    return cost[last]%Mod;
}

int main()
{

    fastread();

    ll i,j,p,n,m,a,sum=0,k,t,b,c,d,cnt=0,q,l,r;


    bool flag=true;




    ll id=1;

    cin>>n>>m;

    string str[n+2];

    for(i=0; i<n; ++i)
        cin>>str[i];

    indeg[1]=1;

    for(i=0; i<n; i++)
    {
        id=(m*i)+1;



        for(j=0; j<m; j++,id++)
        {
            if(str[i][j]=='.' && indeg[id])
            {


                if(j+1<m && str[i][j+1]=='.' )
                    addEdege(id,id+1);


                if(i+1<n && str[i+1][j]=='.' )
                {
                    addEdege(id,id+m);
                }

            }




        }
    }



    cout<<topsort(1,n*m)<<endl;











}



Measured memory_bytes: 74972
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <map>
#include <set>
#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
#include <iomanip>
#include <assert.h>
#include <math.h>
#include <stack>
#include <queue>
#include <list>
using namespace std;

// #define __DEBUG__

#ifdef __DEBUG__
bool debug_disabled = false;
#else
bool debug_disabled = true;
#endif

#define dbg if (debug_disabled) {} else cerr

set<int> friends[200010];
int color[200010];

int visit(int a, int c) {
    color[a] = c;
    dbg << "a = " << a << ", c = " << c << endl;
    int res = 1;
    for (auto iter = friends[a].begin(); iter != friends[a].end(); ++iter) {
        int f = *iter;
        dbg << "\tf = " << f << endl;
        if (color[f] == 0) {
            res += visit(f, c);
        }
    }
    return res;
}

void solve() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int x, y;
        cin >> x >> y;
        friends[x].insert(y);
        friends[y].insert(x);
    }
    int hi = -1;
    int c = 1;
    for (int i = 1; i <= n; ++i) {
        if (color[i] == 0) {
            int res = visit(i, c);
            dbg << "res for i = " << i << ", c = " << c << " is " << res << endl;
            if (hi < res) hi = res;
            ++c;
        }
    }
    cout << hi << endl;
}

int main() {
    cout.setf(ios::fixed, ios::floatfield);
    cout.setf(ios::showpoint);
    cout.precision(12);
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);

    int T = 1;
    // cin >> T;
    for (int i = 1; i <= T; ++i) {
        solve();
    }

    return 0;
}


Measured memory_bytes: 48032
#include <iostream>
#include <iomanip> // << fixed << setprecision(xxx)
#include <algorithm> // do { } while ( next_permutation(A, A+xxx) ) ;
#include <vector>
#include <string> // to_string(nnn) // substr(m, n) // stoi(nnn)
#include <complex>
#include <tuple> // get<n>(xxx)
#include <queue>
#include <stack>
#include <map> // if (M.find(key) != M.end()) { }
#include <set> // S.insert(M);
// if (S.find(key) != S.end()) { }
// for (auto it=S.begin(); it != S.end(); it++) { }
// auto it = S.lower_bound(M);
#include <cctype>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib> // atoi(xxx)
using namespace std;

#define DEBUG 0 // change 0 -> 1 if we need debug.
// insert #if<tab> by my emacs. #if DEBUG == 1 ... #end

typedef long long ll;

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

// const int C = 1e6+10;
// const ll M = 1000000007;

int A[8] = {0, 1, 2, 3, 4, 5, 6, 7};
int N, M;
set<int> V[10];

int main () {
  cin >> N >> M;
  for (auto i = 0; i < M; ++i) {
    int a, b;
    cin >> a >> b;
    a--; b--;
    V[a].insert(b);
    V[b].insert(a);
  }
  int ans = 0;
  do {
    bool ok = true;
    for (auto i = 0; i < N-1; ++i) {
      if (V[A[i]].find(A[i+1]) == V[A[i]].end()) {
        ok = false;
        break;
      }
    }
    if (ok) ans++;
  } while (next_permutation(A+1, A+N));
  cout << ans << endl;
}


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

using ll = long long;

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, n) for (int i = 1; i <= (n); ++i)
#define drep(i, n) for (int i = (n)-1; i >= 0; --i)
#define ddrep(i, n) for (int i = n; i > 0; --i)
#define srep(i, s, t) for (int i = s; i < t; ++i)
#define ssrep(i, s, t) for (int i = s; i <= t; ++i)

#define rng(a) a.begin(), a.end()
#define rrng(a) a.rbegin(), a.rend()
#define pb push_back
#define eb emplace_back
#define fi first
#define se second

#define chmax(x, y) (x = max(x, y))
#define chmin(x, y) (x = min(x, y))

using pi = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using ld = long double;

template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
    os << "(" << p.first << "," << p.second << ")";
    return os;
}

template <class T> ostream &operator<<(ostream &os, const vector<T> &v) {
    os << "{";
    rep(i, (int)v.size()) {
        if (i)
            os << ",";
        os << v[i];
    }
    os << "}";
    return os;
}

template <typename T, size_t S> void printArray(const T (&array)[S]) {
    for (auto val : array)
        std::cout << val << ", ";
    std::cout << "\n";
}

const int mod = 1e9 + 7;
const int inf = 1e9 + 5;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << std::setprecision(10);

    int n; std::cin >> n;
    vector<vector<pi>> evidence(n);
    rep(i, n) {
        int a; std::cin >> a;
        rep(j, a) {
            int x, y; std::cin >> x >> y;
            evidence[i].pb({x-1, y});
        }
    }

    auto cnt = [&](int x) {
        int ret = 0;
        bool ok = true;
        rep(i, n) {
            if (!((x>>i)&1)) continue;
            for (auto &p : evidence[i]) {
                if (((x>>p.fi)&1) != p.se) ok = false;
            }
            ret++;
        }
        return (ok ? ret : 0);
    };

    int ans = 0;
    rep(i, 1<<n) {
        chmax(ans, cnt(i));
    }
    std::cout << ans << "\n";
}


Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <unordered_map>
#include <vector>
#include <string.h>
#include <set>

using namespace std;

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl

template<class T> void printvec(const vector<T>& v) {
  for (auto x : v) { cout << x << " "; }
  cout << endl;
}
template<class T> void printtree(const vector< vector<T> >& tree) {
  for (long long i = 0; i < tree.size(); ++i) {
    cout << i + 1 << ": "; printvec(tree[i]);
  }
}
template<class T, class U> void printmap(const map<T, U>& mp) {
  for (auto x : mp) { cout << x.first << "=>" << x.second << endl; }
}

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

#define rep(i, n) for(ll i = 0; i < n; ++i)
#define all(s) s.begin(), s.end()
#define fr first
#define sc second
#define mp make_pair
#define pb push_back

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> triple;
typedef double D;

const ll INF = 1e9;
const ll MOD = 1000000007;  // 1e9 + 7

int main(int argc, char** argv) {
  cin.tie(NULL);
  cout.tie(NULL);
  ios_base::sync_with_stdio(false);
  //cout << setprecision(10) << fixed;

  ll n;
  cin >> n;
  if (n == 2) {
    cout << 1 << endl;
    return 0;
  }

  set<ll> factors; // all factors o n

  {
    factors.insert(n);

    ll now = n;
    ll i = 2;
    while (i * i <= now) {
      if (now % i == 0) {
        factors.insert(i);
        factors.insert(now/i);
      }
      ++i;
    }
  }

  // for (ll factor : factors) {
  //   cout << factor << endl;
  // }

  set<ll> factorsOfMinus; // all factors o n
  {
    factorsOfMinus.insert(n-1);
    ll now = n-1;
    ll i = 2;
    while (i * i <= now) {
      if (now % i == 0) {
        factorsOfMinus.insert(i);
        factorsOfMinus.insert(now/i);
      }
      ++i;
    }
  }

  // for (ll factor : factorsOfMinus) {
  //   cout << factor << endl;
  // }

  // Here, we try all factors of n-1.
  ll ans = 0;
  for (ll factor : factorsOfMinus) {
    if (factors.find(factor) == factors.end()) { // not in factors
      ++ans;
    }
  }

  // Here, we try all factors
  for (ll factor: factors) {
    ll now = n;
    while (now % factor == 0) {
      now /= factor;
    }
    now %= factor;
    if (now == 1) {
      ++ans;
    }
  }

  cout << ans << endl;
}


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

using namespace std;

#define rep(i, n) for(int i = 0; i < (n); i++)
#define repp(i, l, r) for(int i = (l); i < (r); i++)
#define per(i, n) for(int i = ((n)-1); i >= 0; i--)
#define perr(i, l, r) for(int i = ((r)-1); i >= (l); i--)
#define all(x) (x).begin(),(x).end()
#define MOD 1000000007
#define IINF 1000000000
#define LINF 1000000000000000000
#define SP <<" "<<
#define CYES cout<<"Yes"<<endl
#define CNO cout<<"No"<<endl
#define CFS cin.tie(0);ios::sync_with_stdio(false)

typedef long long LL;
typedef long double LD;

struct edge{
  int to;
  int c;
  int d;
};

struct query{
  int id;
  int c;
  LL y;
  int k;
};

vector<vector<edge>> e;
vector<vector<query>> que;
vector<int> depth;
vector<LL> ans;
vector<vector<int>> par;

void dfs(int x,int d){
  depth[x]=d;
  for(auto ch:e[x]){
    if(ch.to!=par[x][0]){
      par[ch.to][0]=x;
      dfs(ch.to,d+1);
    }
  }
}

int sz;
int lca(int x, int y){
  int d=depth[x]-depth[y];
  if(d>0){
    int a=0;
    while(d){
      if(d&1) x=par[x][a];
      a++;
      d>>=1;
    }
  }else if(d<0){
    d=-d;
    int a=0;
    while(d){
      if(d&1) y=par[y][a];
      a++;
      d>>=1;
    }
  }
  if(x==y) return x;
  per(i,sz){
    if(par[x][i]!=par[y][i]){
      x=par[x][i];
      y=par[y][i];
    }
  }
  return par[x][0];
}


LL ttt=0;
vector<LL> total;
vector<int> cnt;

void dfs2(int x){
  for(auto qc:que[x]){
    ans[qc.id]+=qc.k*(ttt-total[qc.c]+cnt[qc.c]*qc.y);
  }
  for(auto ch:e[x]){
    if(ch.to!=par[x][0]){
      ttt+=ch.d;
      total[ch.c]+=ch.d;
      cnt[ch.c]++;
      dfs2(ch.to);
      ttt-=ch.d;
      total[ch.c]-=ch.d;
      cnt[ch.c]--;
    }
  }
}

int main(){
  int n,q;
  cin >> n >> q;
  e=vector<vector<edge>>(n);
  int a,b,c,d;
  rep(i,n-1){
    cin >> a >> b >> c >> d;
    e[a-1].push_back({b-1,c,d});
    e[b-1].push_back({a-1,c,d});
  }
  sz=1;
  int aaa=1;
  while(n>aaa) aaa*=2,sz++;
  par=vector<vector<int>>(n,vector<int>(sz,-1));
  depth=vector<int>(n,0);
  par[0][0]=0;
  dfs(0,0);
  repp(j,1,sz){
    rep(i,n){
      par[i][j]=par[par[i][j-1]][j-1];
    }
  }
  que=vector<vector<query>>(n);
  rep(i,q){
    cin >> c >> d >> a >> b;
    que[a-1].push_back({i,c,d,1});
    que[b-1].push_back({i,c,d,1});
    que[lca(a-1,b-1)].push_back({i,c,d,-2});
  }
  ans=vector<LL>(q,0);
  cnt=vector<int>(n,0);
  total=vector<LL>(n,0);
  dfs2(0);
  rep(i,q){
    cout << ans[i] << endl;
  }
  return 0;
}


Measured memory_bytes: 35636
use std::io::*;
use std::str::FromStr;

fn main() {
    let cin = stdin();
    let mut sc = Scanner::new(cin.lock());

    loop {
        let n: u32 = sc.next();
        let x: u32 = sc.next();

        if n == 0 {
            break;
        }

        let mut cnt: u32 = 0;

        for a in 1..(n + 1) {
            for b in 1..a {
                for c in 1..b {
                    if a + b + c == x {
                        cnt += 1;
                    }
                }
            }
        }

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

/* ========== Scanner ========== */

struct Scanner<R: Read> {
    reader: R,
}

#[allow(dead_code)]
impl<R: Read> Scanner<R> {
    fn new(reader: R) -> Scanner<R> {
        Scanner { reader: reader }
    }

    fn read<T: FromStr>(&mut self) -> Option<T> {
        let token = self
            .reader
            .by_ref()
            .bytes()
            .map(|c| c.unwrap() as char)
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect::<String>();
        if token.is_empty() {
            None
        } else {
            token.parse::<T>().ok()
        }
    }

    fn next<T: FromStr>(&mut self) -> T {
        if let Some(s) = self.read() {
            s
        } else {
            writeln!(stderr(), "Terminated with EOF").unwrap();
            std::process::exit(0);
        }
    }

    fn vec<T: FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.next()).collect()
    }

    fn chars(&mut self) -> Vec<char> {
        self.next::<String>().chars().collect()
    }

    fn char(&mut self) -> char {
        self.chars()[0]
    }
}



Measured memory_bytes: 5032
#include<stdio.h>
#include<set>
#include<algorithm>
using namespace std;
int s[100000];
int p[1000000];
int q[1000000];
int r[1000000];
int ans[100000];
int main(){
	int a,b,c;
	scanf("%d%d%d",&a,&b,&c);
	set<pair<int,int> >S;
	for(int i=0;i<a;i++){
		S.insert(make_pair(0,i));
	}
	for(int i=0;i<b;i++){
		scanf("%d%d%d",p+i,r+i,q+i);
		p[i]--;
	}
	int now=0;
	for(int i=0;i<c;i++){
		while(now<b&&r[now]==i){
			S.erase(make_pair(-s[p[now]],p[now]));
			s[p[now]]+=q[now];
			S.insert(make_pair(-s[p[now]],p[now]));
			now++;
		}
		pair<int,int> M=*(S.begin());
		ans[M.second]++;
	}
	int val=0;
	int at=0;
	for(int i=0;i<a;i++){
		if(val<ans[i]){
			val=ans[i];
			at=i;
		}
	}
	printf("%d\n",at+1);
}

Measured memory_bytes: 17956
# https://atcoder.jp/contests/abc138/tasks/abc138_d

import sys
input = sys.stdin.readline
import marshal


class Graph:
    def __init__(self, n, dictated=False, decrement=True, edge=[]):
        self.n = n
        self.dictated = dictated
        self.decrement = decrement
        self.edge = [set() for _ in range(self.n)]
        self.parent = [-1]*self.n
        self.info = [-1]*self.n
        for x, y in edge:
            self.add_edge(x,y)

    def add_edge(self, x, y):
        if self.decrement:
            x -= 1
            y -= 1
        self.edge[x].add(y)
        if self.dictated == False:
            self.edge[y].add(x)

    def add_adjacent_list(self, i, adjacent_list):
        if self.decrement:
            self.edge[i] = set(map(lambda x:x-1, adjacent_list))
        else:
            self.edge[i] = set(adjacent_list)

    def dfs2(self, info, start, goal=-1, time=0, save=False):
        """
        :param info: 各頂点の付加情報
        :param start: スタート地点
        :param goal: ゴール地点
        :param save: True = 前回の探索結果を保持する
        :return: ゴール地点までの距離。存在しなければ -1
        """

        if self.decrement:
            start -= 1
            goal -= 1
        if not save:
            self.parent = [-1] * self.n

        edge2 = marshal.loads(marshal.dumps(self.edge))

        p, t = start, time
        self.parent[p] = -2
        while True:
            if edge2[p]:
                q = edge2[p].pop()
                if q == self.parent[p] and not self.dictated:
                    """ 逆流した時の処理 """
                    """"""""""""""""""""
                    continue
                if self.parent[q] != -1:
                    """ サイクルで同一点を訪れた時の処理 """
                    """"""""""""""""""""
                    continue
                if q == goal:
                    """ ゴール時の処理"""
                    # return t + 1
                    """"""""""""""""""""
                    continue
                """ p から q への引継ぎ"""
                info[q] += info[p]
                """"""""""""""""""""
                self.parent[q] = p
                p, t = q, t + 1
            else:
                """ 探索完了時の処理 """
                """"""""""""""""""""
                if p == start and t == time:
                    break
                p, t = self.parent[p], t-1
                """ 二度目に訪問時の処理 """

                """"""""""""""""""""
        return info


######################################################################################################

N, Q = map(int, input().split())  # N:頂点数, Q: クエリの数
M = N-1

graph = Graph(N, dictated=False)

for _ in range(M):
    x, y = map(int, input().split())
    graph.add_edge(x,y)

info = [0] * N
for _ in range(Q):
    p, x = map(int, input().split())
    info[p - 1] += x

print(*graph.dfs2(info, start=1))



Measured memory_bytes: 264992
#include <bits/stdc++.h>
#include <numeric>
typedef long long ll;
#define rep(i,a,b) for(int i=a;i<b;++i)
#define rrep(i,a,b) for(int i=a;i>=b;--i)
using namespace std;

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

    string s; cin >> s;
    set<char> chars;
    rep(i, 0, s.size()) chars.insert(s[i]);

    int res = 10000;
    for(auto c : chars) {
        int turns = 0, turnsMax = 0;
        rep(i, 0, s.size()) {
            if (s[i] != c) ++turns;
            if (s[i] == c or i == s.size()-1) {
                turnsMax = max(turnsMax, turns);
                turns = 0;
            }
        }
        res = min(res, turnsMax);
    }

    cout << res << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
	int n;
	cin>>n;
	int a[n];
	for(int i=0;i<n;++i)
		cin>>a[i];
	sort(a,a+n);
	int sum=0;
	for(int i=0;i<n-1;++i)
		sum+=a[i];
	if(sum>a[n-1])
		cout<<"Yes"<<endl;
	else
		cout<<"No"<<endl;
	return 0;
}

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

int main()
{

    vector<vector<int>> c(4, vector<int>(4));

    for (int i = 1; i <= 3; i++)
    {
        for (int j = 1; j <= 3; j++)
        {
            cin >> c.at(i).at(j);
        }
    }

    bool right = true;
    int Min = min(c.at(1).at(1), min(c.at(1).at(2), c.at(1).at(3)));
    for (int a1 = 0; a1 <= Min; a1++)
    {
        right = true;
        
        int b1 = c.at(1).at(1) - a1;
        int b2 = c.at(1).at(2) - a1;
        int b3 = c.at(1).at(3) - a1;

        int a2 = c.at(2).at(1) - b1;
        int a3 = c.at(3).at(1) - b1;

        if (a2 < 0 || a3 < 0)
            right = false;

  
        if (a2 + b2 != c.at(2).at(2)) 
            right = false;
        if (a2 + b3 != c.at(2).at(3)) 
            right = false;
        if (a3 + b2 != c.at(3).at(2)) 
            right = false;
        if (a3 + b3 != c.at(3).at(3)) 
            right = false;
        
        if (right) break;
    }

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


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ABC144D_Water_Bottle
{
    class Program
    {
        static void Main(string[] args)
        {
            double[] input = Console.ReadLine().Split(' ').Select(z => double.Parse(z)).ToArray();
            double a = input[0];
            double b = input[1];
            double x = input[2];

            if (a * a * b / 2 <= x)
            {
                double theta = (Math.Atan((2 / a) * (b - (x / (a * a))))) * (180 / Math.PI);
                Console.WriteLine(theta);
            }
            else
            {
                double theta = (Math.Atan(a * b * b / (2 * x))) * (180 / Math.PI);
                Console.WriteLine(theta);
            }
        }
    }
}


Measured memory_bytes: 13268
N = int(input())
a = list(map(int, input().split()))
right = 0
summ = 0
ans = 0
for left in range(N):
    while right<N and summ ^ a[right] == summ + a[right]:
        summ += a[right]
        right+=1
    ans += right - left
    if left == right:
        right+=1
    else:
        summ-=a[left]
print(ans)

Measured memory_bytes: 24712
#include<bits/stdc++.h>
#include<string.h>
 
typedef long long int ll;
#define all(x) (x).begin(), (x).end()
 
using namespace std;

int nxt() {
    int x;
    cin >> x;
    return x;
}

ll nxtl(){
    ll x;
    cin>>x;
    return x;
}
 
void SieveOfEratosthenes(int n,vector <int> &primes) 
{ 
    // Create a boolean array "prime[0..n]" and initialize 
    // all entries it as true. A value in prime[i] will 
    // finally be false if i is Not a prime, else true. 
    bool prime[n+1]; 
    memset(prime, true, sizeof(prime)); 
  
    for (int p=2; p*p<=n; p++) 
    { 
        // If prime[p] is not changed, then it is a prime 
        if (prime[p] == true) 
        { 
            // Update all multiples of p greater than or  
            // equal to the square of it 
            // numbers which are multiple of p and are 
            // less than p^2 are already been marked.  
            for (int i=p*p; i<=n; i += p) 
                prime[i] = false; 
        } 
    } 
  
    // Print all prime numbers 
    for (int p=2; p<=n; p++) 
       if (prime[p]) 
          primes.push_back(p);
} 
 
ll max(ll a,ll b)
{
    if(a>b)
        return a;
    return b;
}
 
ll power(ll x, ll y,ll mod) 
{ 
    ll temp; 
    if( y == 0) 
        return 1; 
    temp = power(x, y/2,mod); 
    if (y%2 == 0) 
        return (temp*temp)%mod; 
    else
        return (((x*temp)%mod)*temp)%mod; 
}

vector <char> ans2;
void cal(vector <char> &v,string s,int i,vector <char> temp);

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string s;
    cin>>s;
    vector <char> v(2);
    v[0]='+';
    v[1]='-';    

    vector <char> temp;
    cal(v,s,0,temp);
    for(int i=0;i<3;i++)
        cout<<s[i]<<ans2[i];
    cout<<s[3]<<"=7"<<endl;

    
    return 0;   
}

void cal(vector <char> &v,string s,int i,vector <char> temp)
{
    if(i==3)
    {
        ll y=s[0]-48;
        if(temp[0]=='+')
            y+=(s[1]-48);
        else
            y-=(s[1]-48);
        if(temp[1]=='+')
            y+=(s[2]-48);
        else
            y-=(s[2]-48);
        if(temp[2]=='+')
            y+=(s[3]-48);
        else
            y-=(s[3]-48);
        if(y==7)
        {
            ans2=temp;
        }
        //cout<<y<<endl;

    }
    else
    {
        for(int j=0;j<2;j++){
            temp.push_back(v[j]);
            cal(v,s,i+1,temp);
            temp.pop_back();
        }
    }
}




 
 


Measured memory_bytes: 256
using System;

namespace A
{
    class Program
    {
        static void Main(string[] args)
        {
            string A = Console.ReadLine();
            if (A[0]!=A[1]|| A[0] != A[2])
            {
                Console.WriteLine("Yes");

            }
            else
            {
                Console.WriteLine("No");
            }
        }
    }
}


Measured memory_bytes: 11092
#include <iostream>
#include <string>
using namespace std;
string a;
long long ans,n,c[26];
int main(){
    cin>>a;
    n=a.size();
    ans=n*(n-1)/2;
    for(int i=0;i<n;i++)c[a[i]-'a']++;
    for(int i=0;i<26;i++)ans-=(c[i]-1)*c[i]/2;
    cout<<ans+1<<endl;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define all(a) (a).begin(),(a).end()
#define rep(i,n) for(ll i=0,i##_len=(n);i<i##_len;i++)
#define rep2(i,a,b) for(ll i=(a),i##_len=(b);i<=i##_len;i++)
#define rrep(i,n) ll i=(n);ll now=-1;while(i--&&(now++||1))
#define Yes(n) cout<<((n)?Yes:No)<<"\n"
#define vll vector<ll>
#define pb push_back

using namespace std;
using ll = long long;

static inline void ignore_ret(int x) {x++;}
template<class T> bool chmax(T&a,const T&b){if(a<b){a=b;return true;}return false;}
template<class T> bool chmin(T&a,const T&b){if(a>b){a=b;return true;}return false;}
template<class T> T gcd_vec(vector<T>v){T r=v.at(0);for(T i=1;i<v.size();i++)r=gcd(r,v.at(i));return r;}
template<class T> T lcm_vec(vector<T>v){T r=v.at(0);for(T i=1;i<v.size();i++)r=lcm(r,v.at(i));return r;}
template<class T> T factorial(T n){if(n==0)return 1;T r=1;for(T i=2;i<=n;i++)r*=i;return r;}
template<class T> T nCr(T n,T k){return factorial<T>(n)/(factorial<T>(k)*factorial<T>(n-k));}
template<class T> T dot_product(vector<T>u,vector<T>v){T r=0;for(T i=0;i<u.size();i++)r+=u.at(i)*v.at(i);return r;}
template<class T> T sum(vector<T>v){return reduce(all(v),0LL);}

// Template ends here

const string Yes = "Yes";
const string No = "No";

void solve(string w){
    vector<int> V(26, 0);
    rep(i, w.size()) V.at(w.at(i) - 'a')++;
    rep(i, 26) if (V.at(i) % 2) {
        cout << "No\n";
        return;
    }
    cout << "Yes\n";
}

int main() {
    string w;
    cin >> w;
    solve(w);
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<math.h>
#include<vector>
#include<map>
#include<string.h>
#include<limits.h>
#define int long long
using namespace std;
 
int mincost[1000][1000];
signed main() {
	int a, b; scanf("%lld%lld", &a, &b);
	int T;cin>>T;
	for (int c = 0; c < a; c++) {
		for (int d = 0; d < a; d++) {
			mincost[c][d] = LLONG_MAX/3;
		}
		mincost[c][c] = 0;
	}
	for (int c = 0; c < b; c++) {
		int d, e, f; scanf("%lld%lld%lld", &d, &e, &f);
		mincost[d][e]=f;
	}
	for (int x = 0; x < a; x++) {
		for (int y = 0; y < a; y++) {
			for (int z = 0; z < a; z++) {
				if (mincost[y][x] != LLONG_MAX/3&& mincost[x][z] != LLONG_MAX/3) {
					mincost[y][z] = min(mincost[y][z], mincost[y][x] + mincost[x][z]);
				}
			}
		}
	}
	for (int i = 0; i < a; i++) {
		if (mincost[T][i]!=LLONG_MAX/3&&mincost[i][i] < 0) {
			puts("NEGATIVE CYCLE");
			return 0;
		}
	}
	for (int i = 0; i < a; i++) {
		if(mincost[T][i]==LLONG_MAX/3)puts("INF");
		else cout<<mincost[T][i]<<endl;
	}	
}

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

#define MOD 1000000007LL

int prime[168] = { 2,   3,   5,   7,  11,  13,  17,  19,  23,  29,
                 31,  37,  41,  43,  47,  53,  59,  61,  67,  71,
                 73,  79,  83,  89,  97, 101, 103, 107, 109, 113,
                127, 131, 137, 139, 149, 151, 157, 163, 167, 173,
                179, 181, 191, 193, 197, 199, 211, 223, 227, 229,
                233, 239, 241, 251, 257, 263, 269, 271, 277, 281,
                283, 293, 307, 311, 313, 317, 331, 337, 347, 349,
                353, 359, 367, 373, 379, 383, 389, 397, 401, 409,
                419, 421, 431, 433, 439, 443, 449, 457, 461, 463,
                467, 479, 487, 491, 499, 503, 509, 521, 523, 541,
                547, 557, 563, 569, 571, 577, 587, 593, 599, 601,
                607, 613, 617, 619, 631, 641, 643, 647, 653, 659,
                661, 673, 677, 683, 691, 701, 709, 719, 727, 733,
                739, 743, 751, 757, 761, 769, 773, 787, 797, 809,
                811, 821, 823, 827, 829, 839, 853, 857, 859, 863,
                877, 881, 883, 887, 907, 911, 919, 929, 937, 941,
                947, 953, 967, 971, 977, 983, 991, 997 };
int exponent[168] = {0};

void count(int N) {
    int i, j, p;
    for (i=2;i<=N;i++) {
        j = 0;
        while (j<168) {
            p = i;
            while (p%prime[j] == 0) {
                exponent[j]++;
                p /= prime[j];
            }
            j++;
        }
    }
}

int main(void) {
    int i, N;
    long long c;

    scanf("%d", &N);
    count(N);

    c = 1LL;
    for (i=0;i<168;i++) {
        c *= (long long)(exponent[i]+1);
        c %= MOD;
    }
    printf("%lld\n", c);
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll, ll>;
const ll INF = 1e18;
#define print(x) cout << (x) << endl;
#define rep(i,m,n) for(ll i = (m); i < (n); i++)

int main()
{
    // 入力
    int n; // 都市数
    cin >> n;
    vector<vector<long double> > dist(n, vector<long double>(n)); // 各都市間の所要時間
    vector<vector<long double> > xy(n, vector<long double>(2)); // 各都市間の所要時間


    for (int i = 0; i < n; ++i) {
            cin >> xy.at(i).at(0);
            cin >> xy.at(i).at(1);
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            dist[i][j] = sqrt((xy.at(i).at(0)-xy.at(j).at(0))*(xy.at(i).at(0)-xy.at(j).at(0))+(xy.at(i).at(1)-xy.at(j).at(1))*(xy.at(i).at(1)-xy.at(j).at(1)));
        }
    }

    // 初期順列
    vector<int> order(n);
    for (int i = 0; i < n; ++i) order[i] = i;
    
    long double sum = 0;
    ll count = 0;
    do {
        /* 順序 order についての所要時間を計算 */
        int temp_dist = 0;
        for (int i = 1; i < n; ++i) {
            sum += dist[order[i-1]][order[i]];
        }
            count++;
        // /* 暫定値より小さかったら更新 */
        // if (temp_dist < res) {
        //     res = temp_dist;
        // }
    } while (next_permutation(order.begin(), order.end()));

    // 答えを出力
    cout << setprecision(16) << sum/count << endl;
}


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

using namespace std;
const int maxn=2e5+111;
int N, a[maxn];
long long ans=0;
priority_queue<int> q;

int main(){
    scanf("%d", &N);
    for (int i=0; i<N; i++) scanf("%d", &a[i]);
    sort(a, a+N);
    q.push(a[N-1]);
    for (int i=N-2; i>=0; i--){
        int x=q.top(); q.pop();
        ans+=x;
        q.push(a[i]);
        q.push(a[i]);
    }
    printf("%lld\n", ans);
}

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

int main(){
    int N;
    cin >> N;
    
if(N < 1200){
    cout <<"ABC"<<endl;
}else if ( N <2800){
    cout << "ARC" << endl;
}else{
    cout << "AGC" << endl;
}

}


Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

killed = 0

for i in range(n):
    now_kill = min(a[i], b[i])
    killed += now_kill
    #a[i] -= now_kill
    b[i] -= now_kill
    if b[i] == 0:continue
    now_kill = min(a[i+1], b[i])
    killed += now_kill
    a[i+1] -= now_kill
    #b[i] -= now_kill

print(killed)

Measured memory_bytes: 18476
#include <iostream>
#include <iomanip> // << fixed << setprecision(xxx)
#include <algorithm> // do { } while ( next_permutation(A, A+xxx) ) ;
#include <vector>
#include <string> // to_string(nnn) // substr(m, n) // stoi(nnn)
#include <complex>
#include <tuple> // get<n>(xxx)
#include <queue>
#include <stack>
#include <map> // if (M.find(key) != M.end()) { }
#include <set> // S.insert(M);
// if (S.find(key) != S.end()) { }
// for (auto it=S.begin(); it != S.end(); it++) { }
// auto it = S.lower_bound(M);
#include <random> // random_device rd; mt19937 mt(rd());
#include <cctype>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib> // atoi(xxx)
using namespace std;

#define DEBUG 0 // change 0 -> 1 if we need debug.
// insert #if<tab> by my emacs. #if DEBUG == 1 ... #end

typedef long long ll;

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

// const int C = 1e6+10;
// const ll M = 1000000007;

bool flush(ll n) {
  assert(1 <= n && n <= 1000000000000000000);
  cout << "? " << n << endl;
  char c;
  cin >> c;
  return (c == 'Y');
}

void answer(ll n) {
  assert(1 <= n && n <= 1000000000);
  cout << "! " << n << endl;
}

int main () {
  ll N = 0;
  while (N < 1000000000) {
    int ub = 9;
    int lb = ((N == 0) ? 0 : -1);
    while (ub - lb > 1) {
      int t = (ub + lb)/2;
      string str = to_string(N) + to_string(t);
      while (stoll(str) <= 1000000000) {
        str = str + "9";
      }
      ll now = stoll(str);
      if (flush(now)) {
        ub = t;
      } else {
        lb = t;
      }
    }
    N = stoll(to_string(N) + to_string(ub));
  }
  while (N % 10 == 0) {
    ll temp = N/10 + 1;
    ll temp2 = temp;
    while (temp2 % 10 == 0) {
      temp2 /= 10;
    }
    if (temp2 != 1) {
      if (flush(temp)) {
        N = N/10;
      } else {
        break;
      }        
    } else {
      if (!flush(temp)) {
        N = N/10;
      } else {
        break;
      }        
    }
  }
  answer(N);
}


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

#define Imposter ios_base::sync_with_stdio(false);cin.tie(NULL);
#define pb push_back
#define ll long long int
#define mp make_pair
#define se second
#define fi first

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("O3")
using namespace __gnu_pbds;
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>//s.order_of_key(val) *s.find_by_order(ind)

using namespace std;
#define f(n) for(ll i=0;i<n;i++)
#define rep(i,a,b) for(i=a;i<b;i++)
#define input(arr,n) for(ll i1=0;i1<n;i1++ )cin>>arr[i1]
#define vll vector<ll>
#define vlll vector<vll>
#define all(x) x.begin(),x.end()
const int maxx = 200005; 
vector<ll> adj[maxx]; 
ll power(ll x, ll y, ll p) {
    ll res = 1;    x = x % p;
    while(y > 0) {
        if(y & 1) res = (res*x) % p;
        y = y>>1;    x = (x*x) % p;
    } return res;
}
void dfs(int curr, int& cnt, int*  
             visited, vector<ll>& duringdfs) 
{ 
    visited[curr] = 1; 
  
    ++cnt; 
    duringdfs.push_back(curr); 
    for (auto& child : adj[curr]) { 
 
        if (visited[child] == 0) { 
            dfs(child, cnt, visited, duringdfs); 
        } 
    } 
} 
void MaximumVisit(ll n) 
{ 

    int visited[n+1]; 
    memset(visited, 0, sizeof visited); 
    int ans[n+1]; 
    memset(ans, 0, sizeof ans); 
    vector<ll> duringdfs;  
    for (int i = 1; i <= n; ++i) { 
        duringdfs.clear(); 
        int cnt = 0; 
        if (visited[i] == 0) { 
            cnt = 0; 
            dfs(i, cnt, visited, duringdfs); 
        } 
        for (auto& x : duringdfs) { 
            ans[x] = cnt; 
        } 
    } 
    ll maxi=*max_element(ans,ans+n+1);
    cout<<maxi<<endl;
    
    return; 
} 

int main()
{
    Imposter

    ll n,m;
    cin>>n>>m;set<pair<ll,ll>>s;
    f(m)
    {
        ll a,b;
        cin>>a>>b;
        if(s.find(make_pair(a,b))==s.end())
        {
            adj[a].pb(b);
            adj[b].pb(a);
        }
        s.insert(make_pair(a,b));

    }
    MaximumVisit(n); 
    return 0;
}


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

int main()
{
    int n;
    cin>>n;
    int a[n],b[n],c[n];
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0;i<n;i++)
        cin>>b[i];
    for(int i=0;i<n;i++)
       c[i]=a[i]-b[i];
    sort(c,c+n);
    int sum=0;
     for(int i=0;i<n;i++)
     {
         if(c[i]>0) sum=sum+c[i];
     }
     cout<<sum<<endl;
     return 0;
}


Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scn = new Scanner(System.in);
        int A = scn.nextInt();
        int B = scn.nextInt();
        int K = scn.nextInt();
        ArrayList<Integer> hits = new ArrayList<Integer>();
        int cnt = 0;
        for(int i=1; i<=100; i++) {
            if(A%i == 0 && B%i == 0) hits.add(i);
        }
        System.out.println(hits.get(hits.size() - K));
        scn.close();
    }
}

Measured memory_bytes: 23892
n=int(input())
robots=[]
for i in range(n):
    x,l=map(int,input().split())
    robots.append([x-l,x+l])

robots.sort(key=lambda x:x[1])
now_d=-9999999999999999999
ans=0
for ri in robots:
    if(now_d<=ri[0]):
        ans+=1
        now_d=ri[1]
print(ans)

Measured memory_bytes: 21360
// AOJ DPL_5_J Balls and Boxes 10
// n 個の区別できないボールを k 個の区別できない箱に入れる
// とき、可能な入れ方の総数を求めてください。
// ただし、
//    どのボールも、必ずいずれかの箱に入れる。
//    ボールが1つも入っていない箱があってもよい。
// 答えは制限付き分割数 divnum(n, k)
// 2019.3.11 bal4u

#include <stdio.h>
#include <stdlib.h>

#define MOD 1000000007
int tbl[1001][1001];

int divnum(int n, int k)
{
	int ans;

	if (tbl[n][k]) return tbl[n][k];
	if (n < 0) return 0;
	if (n == 0 || n == 1 || k == 1) return 1;
	else {
		ans = divnum(n, k - 1);
		if (n >= k) ans += divnum(n - k, k);
	}
	return tbl[n][k] = ans % MOD;
}

int main()
{
	int n, k;

	scanf("%d%d", &n, &k);
	printf("%d\n", divnum(n, k));
	return 0;
}


Measured memory_bytes: 5744
#include<iostream>
#include<string.h>
#include<vector>
#include<list>
#include<stdio.h>
#include<math.h>
#include<iomanip>
#include<map>
#include<stack>
#include<queue>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) range(i,0,b)
#define debug(x) cout << "debug " << x << endl;
using namespace std;

int main(){
    double x, y, pri;
    while(cin >> x >> y >> pri, x||y||pri){
        int max = 0;
        double xt = x / 100 + 1;
        double yt = y / 100 + 1;
        for(double i = 1; i < pri; i++){
            for(double j = i; j < pri; j++){
                if(i + j > pri) break;
                int a = i * xt + 0.000001;
                int b = j * xt + 0.000001;;
                int beforePrice = a + b;
                if(beforePrice == pri){
                    int c = i * yt + 0.000001;;
                    int d = j * yt + 0.000001;;
                    int afterPrice = c + d;
                    if(max < afterPrice) max = afterPrice;
                }
            }
        }
        cout << max << endl;
    }
}

Measured memory_bytes: 1224
#include<bits/stdc++.h>
using namespace std;
int main(){

	char S[100];

	cin >> S;

	if((S[6] == 52 || S[6] < 52) && (S[5] == 48)){
		printf("Heisei\n");
	}
    else{
    	printf("TBD\n");
    }
  
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
 
using namespace std;
 
int32_t main ()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);

	int n;
	cin>>n;
	bool ans=0;
	int count=0;
	for(int i=0;i<n;i++){
		int x,y;
		cin>>x>>y;
		if(x==y)count++;
		else count=0;
		if(count>=3)ans=1;
	}	

	if(ans)cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	
	return 0;
}


Measured memory_bytes: 3640
//{{{
#include <bits/stdc++.h>
using namespace std;
#define repX(a,b,c,x,...) x
#define repN(a) repX a
#define rep(...) repN((__VA_ARGS__,rep3,rep2,loop))(__VA_ARGS__)
#define rrep(...) repN((__VA_ARGS__,rrep3,rrep2))(__VA_ARGS__)
#define loop(n) rep2(i_,n)
#define rep2(i,n) rep3(i,0,n)
#define rep3(i,begin,end) for(int i=(int)(begin),i##_end=(int)(end);i<i##_end;++i)
#define rrep2(i,n) rrep3(i,n,0)
#define rrep3(i,begin,end) for(int i=(int)(begin-1),i##_end=(int)(end);i>=i##_end;--i)
#define foreach(x,a) for(auto&x:a)
using ll=long long;
const ll mod=(ll)1e9+7;
//}}}

int color[100000];
vector<pair<int, ll>> vv[100000];

int main(){
  int N, M;
  cin >> N >> M;
  rep(i, N){
    color[i] = -1;
  }
  rep(i, M){
    int u, v, w;
    cin >> u >> v >> w;
    u--;
    v--;
    vv[u].emplace_back(v, w);
    vv[v].emplace_back(u, w);
  }
  int ans = 0;
  rep(i, N){
    if(color[i] == -1){
      ans++;
      stack<int> st;
      color[i] = 0;
      st.push(i);
      while(st.size()){
        int a = st.top();
        int current_color = color[a];
        st.pop();
        for(auto &x: vv[a]){
          int y = x.first;
          if(color[y] == -1){
            color[y] = 0;
            st.push(y);
          }
        }
      }
    }
  }
  cout << ans << endl;
  return 0;
}


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

using namespace std;
int xxx(int y)
{
	return y * y;
}

int main()
{
	int n, y;
	cin >> n >> y;
	for (int i = 0; i <=n;i++)
	{
		for (int j = 0; j <=n;j++)
		{
			if (i + j > n)
			{
				continue;
			}
			if (i * 10000 + j * 5000 + (n - (i + j)) * 1000 == y)
			{
				cout <<i<<" "<<j<<" "<<n-i-j << endl;
				return 0;
			}
			
		}
	}
	cout << -1<<" "<< -1<<" " << -1 << endl;
}


Measured memory_bytes: 256
require 'prime'

n = gets.to_i
if n == 1
  puts 1
else
  h = Prime.prime_division(n).to_h
  p = []
  h.each do |k, v|
    while v > 0
      p << k
      v -= 1
    end
  end
  min = Float::INFINITY
  0.upto(2 ** p.size - 1) do |bit|
    a = 1
    b = 1
    p.size.times do |i|
      if bit[i] == 0
        a *= p[i]
      else
        b *= p[i]
      end
    end
    min = [a.to_s.size, b.to_s.size].max if min > [a.to_s.size, b.to_s.size].max
  end
  puts min
end

Measured memory_bytes: 14416
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rng(i, a, b) for (int i = int(a); i < int(b); i++)
#define rep(i, b) rng(i, 0, b)
#define gnr(i, a, b) for (int i = int(b) - 1; i >= int(a); i--)
#define per(i, b) gnr(i, 0, b)
#define bg begin()
#define ed end()
#define all(x) x.bg, x.ed
#define vi vector<int>
template <class t, class u>
bool chmax(t &a, u b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
template <class t, class u>
bool chmin(t &a, u b)
{
    if (b < a)
    {
        a = b;
        return true;
    }
    return false;
}

ll mod = 1000000007;

signed main()
{
    int n;
    cin >> n;
    vi a(n);
    vi b(n);
    rep(i, n)
    {
        cin >> a[i];
    }
    rep(i, n)
    {
        cin >> b[i];
    }
    ll ans = 0;
    ll rest = 0;
    priority_queue<int> pq;
    rep(i, n)
    {
        if (a[i] < b[i])
        {
            ans++;
            rest += b[i] - a[i];
        }
        else
        {
            pq.push(a[i] - b[i]);
        }
    }
    while (rest > 0)
    {
        if (pq.size() == 0)
        {
            cout << -1 << endl;
            return 0;
        }
        int d = pq.top();
        pq.pop();
        rest -= d;
        ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4652