akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef long double ld;
const int inf=1e9+7;
const ll longinf=1LL<<60;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define F first
#define S second

const int mx=200010;
//const ll mod=1e9+7;
const ll mod=998244353;

struct mint {
    ll x; // typedef long long ll;
    mint(ll x=0):x((x%mod+mod)%mod){}
    mint& operator+=(const mint a) { if ((x += a.x) >= mod) x -= mod; return *this; }
    mint& operator-=(const mint a) { if ((x += mod-a.x) >= mod) x -= mod; return *this; }
    mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this; }
    mint operator+(const mint a) const { mint res(*this); return res+=a; }
    mint operator-(const mint a) const { mint res(*this); return res-=a; }
    mint operator*(const mint a) const { mint res(*this); return res*=a; }
    mint pow(ll t) const { if (!t) return 1; mint a = pow(t>>1); a *= a; if (t&1) a *= *this; return a; }
    // for prime mod
    mint inv() const { return pow(mod-2); }
    mint& operator/=(const mint a) { return (*this) *= a.inv(); }
    mint operator/(const mint a) const { mint res(*this); return res/=a; }
};

int main(){
  int n,s;
  cin >> n >> s;
  vector<int> a(n);
  rep(i,n){
    cin >> a[i];
  }

  vector<vector<vector<mint>>> dp(3010, vector<vector<mint>>(3010, vector<mint>(3,0)));
  dp[0][0][0]=1;
  rep(i,n)rep(j,s+1){
    dp[i+1][j][0] += dp[i][j][0];
    dp[i+1][j][1] += dp[i][j][1] + dp[i][j][0];
    dp[i+1][j][2] += dp[i][j][2] + dp[i][j][1] + dp[i][j][0];
    if(j+a[i]<=s){
      dp[i+1][j+a[i]][1] += dp[i][j][1] + dp[i][j][0];
      dp[i+1][j+a[i]][2] += dp[i][j][1] + dp[i][j][0];
    }
  }
  ll ans = dp[n][s][2].x;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 496128
#include <bits/stdc++.h>
//#include<iostream>
using namespace std;
#define int long long

#define rep(i,s,n) for(int i = s;i<n;i++)
#define repe(i,s,n) for(int i = s;i<=n;i++)
#define rrep(i,s,n) for(int i = (n)-1;i>=(s);i--)
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef pair<int,int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
typedef pair<pint,int> P1;
typedef pair<int,pint> P2;
static const ll maxLL = (ll)1 << 62;
const ll MOD=1000000007;
const ll INF=1e18;
int dy[]={-1,0,1,0};
int dx[]={0,1,0,-1};

int V,E;

struct UF{
    vector<int>par,sz;
    void init(int n){
        par.resize(n);
        sz.resize(n);
        for(int i=0;i<n;i++){
            par[i]=i;
            sz[i]=1;
        }
    }
    int find(int x){
        return x==par[x]?x:par[x]=find(par[x]);
    }
    void unite(int x,int y){
        x=find(x);y=find(y);
        if(x==y)return;
        sz[x]+=sz[y];
        par[y]=x;
    }
    bool same(int x,int y){
        return find(x)==find(y);
    }
    int size(int x){
        return sz[find(x)];
    }
};

signed main(){
    cin.tie(0);
	ios::sync_with_stdio(false);
    cin>>V>>E;
    UF uf;
    uf.init(V);
    vector<P2> v;
    rep(i,0,E){
        int a,b,c;
        cin>>a>>b>>c;
        v.pb(P2(c,pint(a,b)));
    }
    sort(all(v));
    
    int ans=0;
    rep(i,0,E){
        P2 p=v[i];
        if(uf.same(p.se.fi,p.se.se))continue;
        uf.unite(p.se.fi,p.se.se);
        ans+=p.fi;
    }
    cout<<ans<<endl;
    
    
    
    
    
    
    
    
    return 0;
}


Measured memory_bytes: 6148
import java.io.PrintWriter

val pw = PrintWriter(System.out)
fun main(args: Array<String>) {
    func()
    pw.flush()
}
fun println(value: Any) { pw.println(value) }

//ABC129x_x
fun func() {
    val (N, K) = listOfInt()
    var C = next().substring(0, N).toCharArray()
    C[K-1] = C[K-1].toLowerCase()
    println("${C.joinToString(separator = "")}")
}

fun next() = readLine()!!
fun listOfString() = next().split(" ")
fun listOfInt() = listOfString().map { Integer.parseInt(it) } //{ it.toInt() }


Measured memory_bytes: 35948
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;

long long cnt;
int l;
int A[1000000];
int n;
vector<int> G;

// ??????g????????????????????\?????????
void insertionSort(int A[], int n, int g) {
    for (int i = g; i < n; i++) {
        int v = A[i];
        int j = i - g;
        while (j>= 0 && A[j] > v) {
            A[j + g] = A[j];
            j -= g;
            cnt++;
        }
        A[j + g] = v;
    }
}

void shellSort(int A[], int n) {
    // ??°???G = {1, 4, 13, 40, 121, 364, 1093, ...} ?????????
    for (int h = 1; ; ) {
        if (h > n) break;
        G.push_back(h);
        h = 3 * h + 1;
    }
    for (int i = G.size()-1; i >= 0; i--) {
        insertionSort(A, n, G[i]);
    }
}

int main() {
    cin >> n;
    // ??????????????\???scanf??¢??°????????¨
    for(int i = 0; i < n; i++) scanf("%d", &A[i]);
    cnt = 0;

    shellSort(A, n);

    cout << G.size() << endl;
    for (int i = G.size()-1; i >= 0; i--) {
        printf("%d", G[i]);
        if ( i ) printf(" ");
    }
    printf("\n");
    printf("%d\n", cnt);
    for (int i = 0; i < n; i++) {
        printf("%d\n", A[i]);
    }

    return 0;
}

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

int main(void){

int N;
cin >> N;
int l[1100], r[1100];
for (int i = 0; i < N; i++) cin >> l[i] >> r[i];

int count = 0;
for(int i = 0; i < N; i++){
  count += ((r[i]- l[i]) + 1);
}

cout << count;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define pi 2*asin(1.0)


//template functions
/////////////////////////
long Comb(long N,long M){// nCm
long ans=1;
for(long i=N;i>N-M;i--){
    ans=ans*i;
}
for(long i=M;i>0;i--){
    ans=ans/i;
}
return ans;
}
long Perm(long N,long M){// nPm
long ans=1;
for(long i=N;i>N-M;i--){
    ans=ans*i;
}
return ans;
}
/////////////////////////



//Answer


int main() {

long long N;
cin>>N;
if(N%2==1){
    cout<<0<<endl;
}else{
    long long count=0;
	long long M=10;
    for(int i=1;N>=M;i++){
       count+=N/M;
      M=M*5;
    }
    cout<<count<<endl;
}

}

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

int main(){
  int N;
  cin >> N;
  vector<int> H(N);
  for (int i = 0; i < N; i++) {
    cin >> H.at(i);
  }
  int cnt = 1;
  int hmax = H.at(0);
  for (int i = 1; i < N; i++) {
    if (H.at(i) >= hmax){
      hmax = H.at(i);
      cnt++;
    };
  }
  cout << cnt << endl;
}


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

using namespace std;

namespace FastIO {
struct Strs {
  char strs[10000 * 4];
  constexpr Strs() : strs() {
    for (int i = 0; i < 10000; ++i) {
      int j = i;
      for (int t = 3; t >= 0; --t) {
        strs[i * 4 + t] = j % 10 + '0';
        j /= 10;
      }
    }
  }
} constexpr strs;
static constexpr size_t buf_size = 1 << 9;
char buf_in[buf_size], buf_out[buf_size];
size_t pt_in = 0, pt_out = 0, tail_in = 0;
inline size_t num_digits(long long x) {
  if (x >= (long long)1e9) return 10;
  if (x >= (long long)1e8) return 9;
  if (x >= (long long)1e7) return 8;
  if (x >= (long long)1e6) return 7;
  if (x >= (long long)1e5) return 6;
  if (x >= (long long)1e4) return 5;
  if (x >= (long long)1e3) return 4;
  if (x >= (long long)1e2) return 3;
  if (x >= (long long)1e1) return 2;
  return 1;
}
inline void load() {
  memcpy(buf_in, buf_in + pt_in, tail_in - pt_in);
  size_t width = tail_in - pt_in;
  tail_in = width + fread(buf_in + width, 1, buf_size - width, stdin);
  pt_in = 0;
}
inline void flush() {
  fwrite(buf_out, 1, pt_out, stdout);
  pt_out = 0;
}
inline void scan(char& c) { c = buf_in[pt_in++]; }
template <class T>
inline void scan(T& x) {
  char c;
  x = 0;
  scan(c);
  while (c >= '0') {
    x = x * 10 + (c & 15);
    scan(c);
  }
}
inline void print(char c) { buf_out[pt_out++] = c; }
template <class T>
inline void print(T x) {
  if (pt_out > buf_size - 32) flush();
  if (x < 0) {
    print('-');
    x = -x;
  }
  size_t digits = num_digits(x);
  int i;
  for (i = pt_out + digits - 4; i > (int)pt_out; i -= 4) {
    memcpy(buf_out + i, strs.strs + (x % 10000) * 4, 4);
    x /= 10000;
  }
  memcpy(buf_out + pt_out, strs.strs + x * 4 + (pt_out - i), 4 + i - pt_out);
  pt_out += digits;
}
inline void print(const char* s) {
  for (int i = 0; s[i] != 0; ++i) print(s[i]);
}
template <class T>
inline void println(T x) {
  print(x);
  print('\n');
}
struct SetUp {
  SetUp() { load(); }
  ~SetUp() { flush(); }
} setup;
}  // namespace FastIO

using FastIO::print;
using FastIO::println;
using FastIO::scan;

int main() {
  int N;
  scan(N);
  int ct = 0;
  char t;
  for (int i = 0; i < N; ++i) {
    char l, r;
    scan(l);
    FastIO::pt_in++;
    scan(r);
    FastIO::pt_in++;
    if (l == r) {
      ct++;
      if (ct >= 3) {
        println("Yes");
        return 0;
      }
    } else {
      ct = 0;
    }
  }
  println("No");
  return 0;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n;
  cin >> n;
  if (n == 0) {
    return 0;
  }

  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a.at(i);
  }
  cout << a.at(a.size() - 1);
  for (int i = a.size() - 2; i >= 0; i--) {
    cout << " " << a.at(i);
  }
  cout << endl;
  return 0;
}



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

using ll = int64_t;

#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 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 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, k; std::cin >> n >> k;
  vi p(n);
  rep(i, n) std::cin >> p[i];
  int sum = 0, ma = 0, r = p.size()-1;
  if (p.size() > k) {
    rep(i, k) sum += p[i];
    srep(i, k+1, n) {
      sum -= p[i-k];
      sum += p[i];
      if (sum <= ma) continue;
      ma = sum, r = i;
    }
  }
  double ans = 0;
  srep(i, r-k+1, r+1) {
    if (p[i] == 0) ans += 1; 
    else ans += (p[i] + 1) / 2.0;
  }
  std::cout << ans << "\n";
}


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

int main(){
    constexpr unsigned long MOD = 1000000007;
    unsigned long N, M;
    string s;
    cin >> N >> M >> s;

    if(equal(s.begin(), s.end() - 1, s.begin() + 1)){
        vector<unsigned long> fib(N + 1);
        fib[0] = 1;
        fib[1] = 1;
        for(unsigned long i = 2; i <= N; ++i){
            fib[i] = fib[i - 1] + fib[i - 2] % MOD;
        }
        cout << (fib[N - 2] + fib[N]) % MOD << endl;
    }else{
        if(N & 1)return 0 & puts("0");
        auto t = find(s.begin(), s.end(), 'R' ^ 'B' ^ s[0]) - s.begin();
        auto k = t | 1UL;
        {
            unsigned long cnt{0};
            for(auto &i : s){
                if(i == s[0])++cnt;
                else{
                    if(cnt & 1)k = min(k, cnt);
                    cnt = 0;
                }
            }
        }
        vector<unsigned long> dp(N + 1), sum(N + 1);
        dp[0] = 1;
        dp[1] = 1;
        sum[0] = 1;
        sum[1] = 1;
        for(unsigned long i = 2; i <= N; ++i){
            dp[i] = sum[i - 2];
            if(i > k + 2)dp[i] += MOD - sum[i - k - 3];
            (sum[i] = sum[i - 2] + (dp[i] %= MOD)) %= MOD;
        }
        unsigned long ans{0};
        for(unsigned long l = 1; l <= k; l += 2)(ans += (l + 1) * dp[N - l - 1] % MOD) %= MOD;
        cout << ans % MOD << endl;
    }
    return 0;
}

Measured memory_bytes: 3716
n, T = list(map(int, input().split()))
t = list(map(int, input().split()))

end = T
ans = T
for i in range(1, n):
    if t[i] < end:
        ans = ans - (end-t[i]) + T
    else:
        ans += T
    end = t[i] + T
    
print(ans)


Measured memory_bytes: 26836
<?php
// $n = (int)trim(fgets(STDIN));
$input = explode(' ', trim(fgets(STDIN)));

$n = (int)$input[0];
$k = (int)$input[1];
$q = (int)$input[2];

$answered = array_fill(1, $n, 0);

for ($i=0; $i < $q; $i++) { 
	$a = (int)trim(fgets(STDIN));
	$answered[$a] += 1;
}

$res = [];
$limit = $q - $k;
foreach ($answered as $a) {
	if ($a > $limit) {
		$res[] = 'Yes';
	}else{
		$res[] = 'No';
	}
}

echo implode(PHP_EOL, $res);

Measured memory_bytes: 15220
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <iomanip>
#include <map>
using namespace std;

void solve(){
  int n; cin >> n;
  string s; cin >> s;
  vector<int> x(s.length());
  int sum = 0;
  x[0] = 0;
  for(int i = 1; i < s.length(); i++){
    if(s[i - 1] == 'W') sum++;
    x[i] = sum;
  }
  sum = 0;
  for(int i = s.length() - 2; i >= 0; i--){
    if(s[i + 1] == 'E') sum++;
    x[i] += sum;
  }
  int ans = 1000000;
  for(int i = 0; i < x.size(); i++){
    ans = min(x[i], ans);
  }
  cout << ans << endl;
  //for(int i = 0; i < x.size(); i++) cout << x[i] << " "; cout << endl;
  return;
}
int main(){
  solve();
  return 0;
}


Measured memory_bytes: 1796
#include<iostream>
using namespace std;
long long n, cnt;

void dfs(long long x, int f)
{
  if(x>n) return;
  if(f==7) cnt++;
  dfs(x*10+3, f|1);
  dfs(x*10+5, f|2);
  dfs(x*10+7, f|4);
}

int main()
{
  cin >> n;
  dfs(0, 0);
  cout << cnt << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll int
#define N 100000
#define f(i, a, b) for (ll i = (ll)a; i <= (ll)b; i++)
#define rf(i, a, b) for (ll i = (ll)a; i >= (ll)b; i--)
#define po pop_back
#define pb push_back
#define lb lower_bound
#define fi first
#define se second
#define debug(x) cout << #x << " = " << x << endl
#define ub upper_bound
#define ibs ios_base::sync_with_stdio(false)
#define cti cin.tie(0)
#define all(x) x.begin(), x.end()
#define PI 3.14159265
#define cot cout.tie(0)
using namespace std;
/**
        * @author :: Sawlani
        *
        */

int main()
{
    string s,t;
   cin >> s >> t;
   ll a,b;
   cin >> a >> b;
   string u;
   cin >> u;

   if(u==s)
   a--;
   if(u==t)
   b--;

   cout << a << " " << b ;  
    


   
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007

long long N;
int sum(long long x) {
  int s = 0;
  while (x) {
    s += x%10;
    x /= 10;
  }
  return s;
}
signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  cin >> N;
  int m = sum(N), d = 0;
  while (N>=10) {
    N -= (N%10);
    N--;
    assert(N%10==9);
    m = max(m, sum(N) + d);
    N /= 10;
    d += 9;
  }
  cout << m << "\n";
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main()
{
    float a[2], b[2], c[2], d[2], k1, k2;
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%f %f %f %f", &a[0], &a[1], &b[0], &b[1]);
        scanf("%f %f %f %f", &c[0], &c[1], &d[0], &d[1]);
        k1 = (b[1]-a[1])/(b[0]-a[0]);
        k2 = (d[1]-c[1])/(d[0]-c[0]);
        if(k1 == k2)
            printf("YES\n");
        else
            printf("NO\n");
    }
}



Measured memory_bytes: 1916
#include <iostream>
#include <cstdio>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <stack>
#include <utility>
#include <numeric>
#include <algorithm>
#include <functional>
#include <cctype>
#include <complex>
#include <string>
#include <sstream>
#include <cassert>
using namespace std;

//common
typedef int  i32;
typedef long long i64,ll;
#define BR "\n"

#define ALL(c) (c).begin(),(c).end()
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define EACH(it,o) for(auto it = (o).begin(); it != (o).end(); ++it)
#define IN(l,v,r) ((l)<=(v) && (v)<(r))

typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii;
typedef long long ll; typedef vector<long long> vl; typedef pair<long long,long long> pll; typedef vector<pair<long long,long long> > vpll;
typedef vector<string> vs; typedef long double ld;

//config
#define MODE_DEBUG
//#define INF 1<<30
//#define EPS 1e-8
//const ll MOD =100000007;

//debug
#ifdef NDEBUG
#define DUMP(x)
#define DUMPLN(x)
#define DEBUG(x)
#define DEBUGLN(x)
#define LINE()
#define LINELN()
#define CHECK(exp,act)
#define STOP(e)
#else
#define DUMP(x)  cerr << #x << " = " << (x)
#define DUMPLN(x)  DUMP(x) <<endl
#define DEBUG(x) DUMP(x) << LINE() << " " << __FILE__
#define DEBUGLN(x) DEBUG(x)<<endl
#define LINE()    cerr<< " (L" << __LINE__ << ")"
#define LINELN()    LINE()<<endl
#define CHECK(exp,act)  if(exp!=act){DUMPLN(exp);DEBUGLN(act);}
#define STOP(e)  CHECK(e,true);if(!(e)) exit(1);
#endif

template<class T> inline string toString(const vector<T>& x) {
	stringstream ss;
	REP(i,x.size()){
		if(i!=0)ss<<" ";
		ss<< x[i];
	}
	return ss.str();
}
template<class T> inline string toString(const vector<vector<T> >& map) {
	stringstream ss;
	REP(i,map.size()){
		if(i!=0)ss<<BR;
		ss<< toString(map[i]);
	}
	return ss.str();
}
template<class K,class V>  string toString(map<K,V>& x) {
	string res;stringstream ss;
	for(auto& p:x)ss<< p.first<<":" << p.second<<" ";
	return ss.str();
}

template<typename T,typename V> inline T mod(T v,V MOD){
	return (v%MOD+MOD)%MOD;
}

#define nextInt(n) scanf("%d",&n)
#define nextLong(n) scanf("%lld",&n)
#define nextDouble(n) scanf("%lf",&n)


ll INF=1LL<<58;
class Main{
public:	
	void run(){
		string a,b;cin >> a >>b;


		REP(i,a.size()){
			bool ok=true;
			REP(j,b.size()){
				if(i+j>=a.size()){ok=false;break;}
				if(b[j]=='_')continue;
				if(b[j]!=a[i+j]){ok=false;break;}
			}
			if(ok){
				cout <<"Yes"<<endl;return;
			}
		}

		cout <<"No"<<endl;return;
	}
};
 int main(){
 	cout <<fixed<<setprecision(15);
	ios::sync_with_stdio(false);
 	Main().run();
 	return 0;
 }


Measured memory_bytes: 1184
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <set>
#include <iostream>
#include <stack>
#include <vector>
#include <string>
#include <map>
#include <cmath>
#include <queue>
#include <random>
#include <chrono>
using namespace std;

int n, m;

const int maxn = 3005;
char s[maxn];

const int mod = 1e9 + 7;
int cnt[maxn];
int dp[maxn][maxn];
int c[maxn][maxn];

void init(){
    c[0][0] = 1;
    for(int i = 1;i < maxn;i++){
        c[i][0] = c[i][i] = 1;
        for(int j = 1;j < i;j++){
            c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
        }
    }
}

typedef pair<int, int> pii;

pii p[maxn];

bool cmp(pii a, pii b){
    if(a.first != b.first)
        return a.first < b.first;
    return a.second > b.second;
}

void add(int &a, int b){
    a += b;
    if(a >= mod)
        a -= mod;
}

int main(){
    init();
    cin >> n >> m;
    scanf("%s", s + 1);
    cnt[0] = 0;
    for(int i = 1;i <= n;i++){
        cnt[i] = cnt[i - 1] + (s[i] == '0');
    }
    for(int i = 1;i <= m;i++){
        scanf("%d%d", &p[i].first, &p[i].second);
    }
    p[m + 1] = make_pair(n + 1, n + 1);
    sort(p + 1, p + m + 2, cmp);
    int tot = 0;
    dp[0][cnt[p[1].first - 1]] = 1;  
    for(int i = 1, j = 1;i <= m;i = j + 1, j = i){
        while(p[j + 1].second <= p[i].second){
            j++;
        }
        int nxt = j + 1;
        int l = p[i].first, r = p[i].second;
        tot++;
        if(p[nxt].first <= r){
            int len = p[nxt].first - l;
            for(int j = 0;j <= cnt[n];j++){
                if(dp[tot - 1][j] == 0)
                    continue;
                int R = min(cnt[r] - j, len);
                int L = max(0, cnt[r] - j - (r - p[nxt].first + 1));
                for(int k = L;k <= R;k++){
                    add(dp[tot][k + j], 1LL * dp[tot - 1][j] * c[len][k] % mod);
                }
            }
        }else{
            int len = r - l + 1;
            for(int j = 0;j <= cnt[n];j++){
                if(dp[tot - 1][j] == 0)
                    continue;
                int num = cnt[r] - j;
                add(dp[tot][cnt[p[nxt].first - 1]], 1LL * dp[tot - 1][j] * c[len][num] % mod);
            }
        }
    }
    int ans = dp[tot][cnt[n]];
    cout << ans << endl;
    return 0;
}


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

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

using namespace std;

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

typedef long long ll;
typedef long double R;
const R EPS=1e-9L; // [-1000,1000]->EPS=1e-8 [-10000,10000]->EPS=1e-7
inline int sgn(const R& r){return(r > EPS)-(r < -EPS);}
inline R sq(R x){return sqrt(max(x,0.0L));}

const int dx[8]={1,0,-1,0,1,-1,-1,1};
const int dy[8]={0,1,0,-1,1,1,-1,-1};
// Problem Specific Parameter:
const int limit = 50;

int n, m;
int a[limit], b[limit];

bool graph[limit][limit];
bool visited[limit];

void dfs(int v) {
  visited[v] = true;
  for(int v2 = 0; v2 < n; ++v2) {
    if(graph[v][v2] == false) continue;
    if(visited[v2] == true) continue;
    dfs(v2);
  }
}

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

  for(int i = 0; i < m; ++i) {
    cin >> a[i] >> b[i];
    a[i]--, b[i]--;
    graph[a[i]][b[i]] = graph[b[i]][a[i]] = true;
  }

  int ans = 0;

  for(int i = 0; i < m; ++i) {
    graph[a[i]][b[i]] = graph[b[i]][a[i]] = false;
    for(int j = 0; j < n; ++j) visited[j] = false;

    dfs(0);

    bool bridge = false;
    for(int j  = 0; j < n; ++j) if(visited[j] == false) bridge = true;
    if(bridge) ans += 1;

    graph[a[i]][b[i]] = graph[b[i]][a[i]] = true;
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void) {
	int a[100]={}, n[110]={}, i=0, j=0;
	
	while(scanf("%d", &a[i])!=EOF){
		if(a[i]!=0){
			n[j]=a[i];
			j++;
		}
		if(a[i]==0){
			printf("%d\n", n[j-1]);
			j--;
		}
		
		i++;
	}
	
	
	return 0;
}

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


int main(){
    ll n,a,b,h[100010];
    cin>>n>>a>>b;
    rep(i,0,n)cin>>h[i];
    
    ll r=1e9+1,l=0,c=a-b,mid;
    while(l+1<r){
        mid=(r+l)/2;
        ll cn=0;
        rep(i,0,n){
            ll tm=(h[i]-b*mid+c-1)/c;
            cn+=max(tm,0LL);
        }
        if(cn<=mid)r=mid;
        else l=mid;
    }
    cout<<r<<endl;
}

    









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

typedef long long int ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;

template<class T,class U> void chmax(T& a, U b) {if(a<b)a=b;}
template<class T,class U> void chmin(T& a ,U b) {if(b<a)a=b;}

#define rep(i, j) for (int i = 0; i < j; i++)
#define all(obj) (obj).begin(), (obj).end()
#define rall(obj) (obj).rbegin(), (obj).rend()
#define debug(x) cerr << #x << ": " << x << endl;
#define int ll

const ll mod = 1e9 + 7;
const ll inf = (1LL << 50);

const string YES = "Yes";
const string NO = "No";
void solve(long long K, long long X){
    if (K * 500 >= X) {
        cout << YES << endl;
    } else {
        cout << NO << endl;
    }
}


signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.precision(10);
    cout << fixed;

    long long K;
    scanf("%lld",&K);
    long long X;
    scanf("%lld",&X);
    solve(K, X);
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
#define int long long
struct edge
{
	int to,cap,cost,rev;
};
int nn=105;
vector<edge>G[105];
int dist[105];
int prevv[105],preve[105];

void add_edge(int from,int to,int cap,int cost)
{
	G[from].pb((edge){to,cap,cost,G[to].size()});
	G[to].pb((edge){from,0,-cost,G[from].size()-1});
}
int D;
int mincost_maxflow(int s,int t,int f)
{
	int res=0;
	while(1)
	{
		//このnはフローを流すグラフの頂点数でありもとのグラフの頂点数ではない!!!!!!
		fill(dist,dist+nn,INF);
		dist[s]=0;
		bool upd=true;
		while(upd)
		{
			upd=false;
			for(int v=0;v<nn;v++)
			{
				if(dist[v]==INF) continue;
				for(int i=0;i<G[v].size();i++)
				{
					edge &e = G[v][i];
					if(e.cap>0 && dist[e.to]>dist[v]+e.cost)
					{
						dist[e.to]=dist[v]+e.cost;
						prevv[e.to]=v;
						preve[e.to]=i;
						upd=true;
					}
				}
			}
		}
		if(dist[t]>=-D) return res;
		int d=f;
		for(int v=t;v!=s;v=prevv[v])
		{
			d = min(d,G[prevv[v]][preve[v]].cap);
		}
		//f-=d;
		res+=d*(D+dist[t]);
		for(int v=t;v!=s;v=prevv[v])
		{
			edge &e = G[prevv[v]][preve[v]];
			e.cap -= d;
			G[v][e.rev].cap += d;
		}
	}
}

int n,m;
vector<P>edge[105];
int dp[105];

int calc(int v){
	if(dp[v] >= 0) return dp[v];
	dp[v] = 0;
	if(v == n-1) return dp[v];
	for(int i=0;i<edge[v].size();i++){
		dp[v] = max(dp[v],calc(edge[v][i].fi)+edge[v][i].sc);
	}
	return dp[v];
}

signed main(){
	cin>>n>>m;
	rep(i,m){
		int x,y,s; cin>>x>>y>>s;
		edge[x].pb(mp(y,s));
	}
	memset(dp,-1,sizeof(dp));
	D = calc(0);
	ll ans = 0;
	rep(i,n){
		rep(j,edge[i].size()){
			int u = i,v = edge[i][j].fi,cs = edge[i][j].sc;
			ans += 200000-cs;
			add_edge(v,u,1,-200000);
			add_edge(v,u,INF,-cs);
		}
	}
	ans += mincost_maxflow(n-1,0,INF);
	cout << ans << endl;
}


Measured memory_bytes: 3292
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (true) {
			int r = sc.nextInt();
			if (r == 0) {
				sc.close();
				break;
			}

			int n = sc.nextInt();

			int[] xl = new int[n];
			int[] xr = new int[n];
			int[] h = new int[n];
			for (int i = 0; i < n; i++) {
				xl[i] = sc.nextInt();
				xr[i] = sc.nextInt();
				h[i] = sc.nextInt();
			}
			int[] cover = new int[2 * r];
			for (int i = 0; i < n; i++) {
				xl[i] += r;
				xr[i] += r;

				int ll = Math.max(0, xl[i]);
				int rr = Math.min(r * 2, Math.max(0, xr[i]));

				int c = h[i];
				for (int j = ll; j < rr; j++) {
					cover[j] = Math.max(cover[j], c);
				}
			}

			// System.out.println(Arrays.toString(cover));
			double res = 100000.0;
			for (int i = 0; i < cover.length; i++) {
				int xx = i - r > 0 ? i - r + 1 : r - i - 1;
				double t1 = cover[i]
						+ r
						* (1 - Math
								.sin(Math.acos((double) Math.abs(r - i) / r)));
				double t2 = cover[i] + r
						* (1 - Math.sin(Math.acos((double) xx / r)));
				res = Math.min(res, Math.min(t1, t2));
			}

			System.out.println(String.format("%.4f", res));
		}
	}
}

Measured memory_bytes: 26284
#include<iostream>
#include<stdio.h>
#include<string>
#include<algorithm>
#include<math.h>
#include<vector>
using namespace std;
#define INF 999999999
#define lint long long
#define rep(i, n) for(int i = 1; i <= (int)(n); i++)
#define rep0(i, n) for(int i = 0; i < (int)(n); i++)
int gcd(int a,int b){return b?gcd(b,a%b):a;}


int main(){
    int x, y;
    cin >> x >> y;
    if (y%2!=0){
        printf("No\n");
        return 0;
    }
    for (int i=0; i<=x; ++i){
        int t = i;
        int k = x - i;
        if (2*t + 4*k == y){
            printf("Yes\n");
            return 0;
        }
    }
    printf("No\n");
    return 0;
}

Measured memory_bytes: 3632
fun main(args: Array<String>) {
    var x = readLine()!!.split(' ')[1].toInt()
    val a = readLine()!!.split(' ').map { it.toInt() }.sorted()
    var cnt = 0
    for (i in a) {
        x -= i
        if (x < 0) break
        cnt++
    }
    if (x > 0) cnt--
    println(cnt)
}


Measured memory_bytes: 38368
#include <iostream>
using namespace std;
int main(){
    int n;
    cin >> n;
    long long a[n+1];
    long long b[n+1];
    a[0]=0;b[0]=0;
    for (int i=1; i<n+1; i++){
        long long x;
        cin >> x;
        a[i]=x;
        b[i]=b[i-1]+x;
    }
    long long ans=1e10;
    for (int i=1; i<n; i++){
        long long cand=abs(b[n]-2*b[i]);
        ans=min(ans,cand);
    }
    cout << ans << endl;
}

Measured memory_bytes: 3328
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;

const long long N = 1e3 + 17;
ll cnt, ans, lnt, sum, n, l1, x, y, a[N][N], mx, b[N][N], m;
pair<ll,ll>pr[N];
vector<ll>v,v2,v3;
map<ll,ll>mp;
bool used[N], t1, t2;
vector<string>sv;

int main()
{
    cin >> n >> m;
    for(ll i = 0; i < n; i ++)
    {
        cin >> x;
        for(ll j = 0; j < x; j++)
        {
            cin >> a[i][j];
            mp[a[i][j]] ++;
            if(!used[a[i][j]] and mp[a[i][j]] == n)
            {
                cnt ++;
                used[a[i][j]] = true;
            }
        }
    }
    cout << cnt;
}


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

int main(){
  int n, l;
  cin >> n >> l;
  if(l + n - 1 < 0){
    cout << (l + (l+n-2)) * (n - 1) / 2 << endl;
  }else if(l > 0){
    cout << (l+1 + (l+n-1)) * (n - 1) / 2 << endl;
  }else{
    cout << (l + (l+n-1)) * n / 2 << endl;
  }
  return 0;
}
           


Measured memory_bytes: 256
using System;
using System.Collections.Generic;

class Program
{
    static void Main(string[] args)
    {
        int n = int.Parse(Console.ReadLine());
        List<int[]> list = new List<int[]>();

        for (int i = 0; i < n; i++) {
            string v = Console.ReadLine();
            int a = int.Parse(v.Split(' ')[0]);
            int b = int.Parse(v.Split(' ')[1]);
            int c = int.Parse(v.Split(' ')[2]);
            list.Add(new int[] { a, b, c });
        }

        for (int i = 0; i < list.Count; i++) {
            List<int> t = new List<int>();
            t.Add(list[i][0]);
            t.Add(list[i][1]);
            t.Add(list[i][2]);

            t.Sort();

            if (t[2] * t[2] == t[0] * t[0] + t[1] * t[1]) {
                Console.WriteLine("YES");
            }
            else {
                Console.WriteLine("NO");
            }
        }
    }
}

Measured memory_bytes: 9232
list = [[0 for i in range(13)] for j in range(4)]
list_dict = {"S":0, "H":1, "C":2, "D":3}

n = int(input())

for i in range(n):
    card = input().split()
    list[list_dict.get(card[0])][int(card[1]) - 1] = 1

for i in range(4):
   for j in range(13):
        if list[i][j] == 0:
            key = [k for k, v in list_dict.items() if v == i][0]
            print(key, j+1)



Measured memory_bytes: 5612
#include <bits/stdc++.h>
using namespace std;
const int MAXN=110;
int N,A[MAXN];
int main()
{
	cin>>N;
	for (int i=1;i<=N;++i) cin>>A[i];
	for (int i=1;i<=N;++i)
		if (!(A[i]&1))
		{
			if (A[i]%3==0 || A[i]%5==0) continue;
			printf("DENIED\n");
			return 0;
		}
	printf("APPROVED\n");
	return 0;
}

Measured memory_bytes: 256
import java.lang.Math.min

fun main(args: Array<String>) {
    val n = readLine()!!.toInt()
    val s = readLine()!!
    var m = n
    var current = s.count { it == 'E' }
    for(i in 0 until n){
        if(s[i] == 'E') current--
        if(i > 0 && s[i-1] == 'W') current++
        m = min(m, current)
    }
    print(m)
}

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i=0; i<n; ++i) cin >> a[i];
    sort(a.begin(), a.end());

    int p = a[n-1];
    int q = 0;
    int m = min(a[0], a[n-1] - a[0]);
    for(int i=1; i + 1 < n; ++i) {
        if(min(a[i], a[n-1]-a[i]) > m) {
            m = min(a[i], a[n-1]-a[i]);
            q = i;
        }
    }

    cout << p << ' ' << a[q] << endl;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define SC scanf
#define PR printf
#define pb push_back
#define mp make_pair
#define SZ(v) ((int)(v).size())
#define rep(i,n) for(int i=0;i<(n);i++)
#define INF 1000000000
#define ll long long
typedef pair<int,int> pii;
typedef pair<pii,int> ppi;
typedef pair<int,pii> pip;
typedef pair<pii,pii> ppp;
typedef vector<int> vi;
typedef vector<pii> vii;
const int xx[4]={1,-1,0,0};
const int yy[4]={0,0,1,-1};
int n;
map<ll,int>cnt;
ll pow2[50];
int main(){
    ios::sync_with_stdio(false);
    pow2[0]=1;
    for(int i=1;i<=30;i++){
    	pow2[i]=pow2[i-1]*2;
//    	cout<<pow2[i]<<' ';
	}
//	cout<<endl;
	cin>>n;
	vector<ll>a(n+1,0);
	for(int i=0;i<n;i++){
		cin>>a[i];
		cnt[a[i]]++;
	}
	sort(a.begin(),a.end());
	reverse(a.begin(),a.end());
//	for(int i=0;i<n;i++)cout<<a[i]<<' ';
//	cout<<endl;
	int ans=0;
	for(int i=0;i<n;i++){
		int pos=0;
		while(a[i]>pow2[pos]){
			pos++;
		}
//		cout<<pow2[pos]<<endl;
		if(cnt[a[i]]>0&&cnt[pow2[pos]-a[i]]>0){
			ans++;
			cnt[a[i]]--;
			cnt[pow2[pos]-a[i]]--;
		}
		if(pow2[pos]==a[i]){
			pos++;
			if(cnt[a[i]]>1){
				ans++;
				cnt[a[i]]-=2;
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 26880
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
template <class T>
inline void rd(T &x) {
	x=0; char c=getchar(); int f=1;
	while(!isdigit(c)) { if(c=='-') f=-1; c=getchar(); }
	while(isdigit(c)) x=x*10-'0'+c,c=getchar(); x*=f;
}
const int mod=998244353;
const int N=3e6+10;
int Pow(int x,int y) {
	int res=1;
	while(y) {
		if(y&1) res=res*(ll)x%mod;
		x=x*(ll)x%mod,y>>=1;
	}
	return res;
}
int fac[N],inv[N];
int C(int n,int m) { return fac[n]*(ll)inv[m]%mod*inv[n-m]%mod; }
void predo(int n) {
	fac[0]=1; for(int i=1;i<=n;++i) fac[i]=fac[i-1]*(ll)i%mod;
	inv[n]=Pow(fac[n],mod-2); for(int i=n;i>=1;--i) inv[i-1]=inv[i]*(ll)i%mod; 
}
int cal(int n,int m,int x) {
	int ans=0;
	for(int i=m&1;i<=x&&i<=n;i+=2)
		ans=(ans+C(n,i)*(ll)C((m-i)/2+n-1,n-1))%mod;
	return ans;
}
int n,m;
int main() {
	predo(3e6);
	rd(n),rd(m);
	int ans1=cal(n,3*m,m);
	int ans2=n*(ll)cal(n,m-1,m)%mod;
	printf("%d\n",(ans1-ans2+mod)%mod);
	return 0;
}

Measured memory_bytes: 23680
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fore(b,c) for(int val0=b;val0<c;val0++)
#define forr(k,c,s) for(int k=c;k<s;k++)
#define pb push_back
#define mmp make_pair
using namespace __gnu_pbds;
using namespace std;
template<typename T>
using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int> ii;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef long double ld;
typedef vector<vii> al;
typedef vector<ll> vl;
const int INF = 1e9;
const ll INFL = 1LL<<61;
int main() {
	ios::sync_with_stdio(0);cout.precision(20);cout.tie(0);cin.tie(0);
	string s;
	cin >> s;
	cout << s.substr(0,3) << '\n';
}



Measured memory_bytes: 3628
num, qnum, = gets.strip.split.map(&:to_i)
str = gets.strip
str << ' '
ary = str.split('AC')
ary[-1] = ary[-1].sub(' ', '')
ary.map!(&:size)

lmap = []
rmap = []
ary.each_with_index do |i, t|
  lmap.push *Array.new(i, 0)
  rmap.push *Array.new(i, 0)
  unless ary.size - 1 == t then
    lmap.push 0, 1
    rmap.push 1, 0
  end
end
llmap = []
total = 0
lmap.each {|i| total += i; llmap << total }
rrmap = []
total = 0
rmap.reverse_each {|i| total += i; rrmap << total }
#p [lmap, rmap]
#p [llmap, rrmap.reverse]

qnum.times do
  ql, qr, = gets.strip.split.map{|i| i.to_i}
  ql -= 1
  qr = num - qr
  #p [ql, qr]
  puts ary.size - 1 - llmap[ql] - rrmap[qr]
end


Measured memory_bytes: 9980
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <set>
using namespace std;
#define LL long long
#define REP(i, a, b) for(int i = a; i <= b; ++i)
#define PER(i, a, b) for(int i = a; i >= b; --i)

inline int read() {
	int x = 0, flag = 1; char ch = getchar();
	while(!isdigit(ch)) {
		if(ch == '-') flag = -1;
		ch = getchar();
	}
	while(isdigit(ch)) {
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return x * flag;
}
double a[1001], ans;
int id, n, x, T;
int main() {
	n = read(); 
	T = read(); x = read();
	REP(i, 1, n) {
		int y = read();
		a[i] = T - 0.006 * y;
		//cout << a[i] << " " << abs(x - a[i]) << endl;
	}
	id = 1; 
	REP(i, 2, n) {
		if(abs(a[i] - x) < abs(a[id] - x)) id = i;
	}
	cout << id << endl;
	return 0;
}
 

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <math.h>
#include <algorithm>
#include <functional>
#include<iostream>
#include <string>
using namespace std;
typedef long long ll;
#define pb pushback
#define fr(i,n) for(int i=0;i<n;i++)
#define fro(i,j,n) for(int i=j;i<n;i++)
#define ifr(i,n) for(int i=n-1;i>=0;i--)


int main() {
    ll x,y;
	cin >> x>> y;
    ll t=0;
    ll a=x;
    ll b=y;
    while(y!=0){
      t=x%y;
      x=y;
      y=t;
    }
      cout << a*b/x << endl;
}


Measured memory_bytes: 256
require 'pp'
n = gets.to_i
arr = []
n.times do |i|
  # x y h
  arr << gets.split.map(&:to_i)
end


arr.select!{|a|a[2] != 0}
if arr.size == 1
  puts [arr[0][0],arr[0][1],1].join(' ')
  exit
end



true_x = true_y = true_h = nil
(0..100).to_a.product((0..100).to_a).each do |(x,y)|
  pre_h = nil
  true_flag = false
  arr.size.times do |i|
    nx, ny, nh = *arr[i]
    # next if nh == 0
    h = nh + (nx - x).abs + (ny - y).abs
    break if pre_h && pre_h != h
    pre_h = h
    # p [i,arr.size-1]
    if i == arr.size - 1
      true_x = x
      true_y = y
      true_h = h
      true_flag = true
    end
  end
  break if true_flag
end
puts [true_x, true_y, true_h].join(' ')


Measured memory_bytes: 2940
#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <sstream>
#include <math.h>
#include <cstring>
#include <algorithm>
#include <queue>
#define INF 1e9
using namespace std;
//for (int i = 0; i < N; i++){}
int N, W;
long long w[101], v[101];
long long dp[101][201010];

int main() {
    cin >> N >> W;
    for (long long i = 0; i < N; i++){
        cin >> w[i] >> v[i];
    }

    for (int tot = 0; tot <= W; tot++) dp[0][tot] = 0;

    for (long long i = 0; i < N; i++){
        for (long long tot = 0; tot <= W; tot++){
            if(tot >= w[i]){
                dp[i+1][tot] = max((dp[i][tot]), (dp[i][tot - w[i]] + v[i]));
            }else{
                dp[i+1][tot] = dp[i][tot];
            }
        }
    }

    long long ans = 0;
    for(int i=0;i<=W;i++){
        ans = max(ans, dp[N][i]);
    }
    cout << ans << endl;
}

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

using namespace std;

void f(unsigned int r, unsigned int d, unsigned int x) {

    for (int i = 0; i < 10; i++) {
        x = r * x - d;
        cout << x << endl;
    }
}


int main() {

    unsigned int r, d, x;
    cin >> r >> d >> x;

    f(r, d, x);

    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;
class Main {
    public static void main(String args[]) {
        Scanner scanner = new Scanner(System.in);
        int a = scanner.nextInt();
        int b = scanner.nextInt();
        int area = a * b;
        int length = 2 * a + 2 * b;
        System.out.println(area + " " + length);

    }
}


Measured memory_bytes: 26120
n = int(input())
min_k = 10000000000
for i in range(1,n//2+1):
    sum_k = 0
    a = str(i)
    b = str(n-i)
    for j in a:
        sum_k += int(j)
    for j in b:
        sum_k += int(j)
    min_k = min(min_k,sum_k)
print(min_k)

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

int main() {
	int n;
	cin>>n;
	int arr[n];
	int ans=0;
	for(int i=0;i<n;i++){
		cin>>arr[i];
		if(i%2==0){
			if(arr[i]%2==1){
				ans++;
			}
		}
	}
	cout<<ans<<endl;
	
	return 0;
}

Measured memory_bytes: 3592
import sys

def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり

N,M = LI()
AB = [LI() for i in range(M)]
del AB[0]

AB.reverse()

# 逆に橋がない状態から1本ずつ橋を加えた時に、不便さがどのくらい減少するかを考える

class UnionFind:
    def __init__(self,n):
        self.par = [i for i in range(n+1)]  # 親のノード番号
        self.rank = [0]*(n+1)
    def find(self,x):  # xの根のノード番号
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    def same_check(self,x,y):  # x,yが同じグループか否か
        return self.find(x) == self.find(y)
    def unite(self,x,y):  # x,yの属するグループの併合
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            x,y = y,x
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
        self.par[y] = x

G = UnionFind(N)
C = [1]*(N+1)  # 連結成分の大きさ(根となっている頂点だけ正しい)

ANS = [N*(N-1)//2]
for a,b in AB:
    if not G.same_check(a,b):
        x = C[G.find(a)]
        y = C[G.find(b)]
        ANS.append(ANS[-1]-x*y)  # 連結成分の積だけ不便さが減少
        G.unite(a,b)
        C[G.find(a)] = x+y  # 連結成分の大きさを変える
    else:
        ANS.append(ANS[-1])

ANS.reverse()

print(*ANS,sep='\n')


Measured memory_bytes: 104748
import numpy as np
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

N = int(input())
WSV = list(tuple(map(int, input().split())) for _ in range(N))
WSV.sort(key=lambda x: x[0] + x[1])


U = 2 * 10 ** 4 + 100
dp = np.zeros(U, dtype=np.int64)
for w, s, v in WSV:
    dp[w:w+s+1] = np.maximum(dp[w:w+s+1], dp[:s+1] + v)

print(dp.max())

Measured memory_bytes: 27772
#include<iostream>
#include<vector>
#include<cstring>

using namespace std;

typedef long long ll;

struct data{
  ll sat,req;
  data():req(0){}
};

const int MAX = 101;
const int LIM = (1<<16);
int N;
ll dp[MAX][LIM];
vector<data> V;

void init(){
  memset(dp,0,sizeof(dp));
  V.clear();
}

void input(){
  for(int i = 0; i < N; i++){
    data d;
    int num;
    cin >> num >> d.sat;
    for(int j = 0; j < num; j++){
      int from,to;
      cin >> from >> to;
      for(int k = from-6; k < to-6; k++) d.req |= (1<<k);
    }
    V.push_back(d);
  }
}

void solve(){

  for(int i = 0; i < V.size(); i++){
    for(int j = 0; j < LIM; j++){
      dp[i+1][j] = max(dp[i+1][j],dp[i][j]);
      if(!(j&V[i].req)) dp[i+1][j+V[i].req] = max(dp[i+1][j+V[i].req],dp[i][j]+V[i].sat);
    }
  }
  ll ans = 0;
  for(int i = 0; i < LIM; i++)
    ans = max(ans,dp[N][i]);
  cout << ans << endl;
}


int main(){
  while(cin >> N && N){
    init();
    input();
    solve();
  }
  return 0;
}

Measured memory_bytes: 52928
/**********************************************
 *Author*        :XzzF
 *Created Time*  : 2018/4/28 21:00:04
 *Ended  Time*  : 2018/4/28 21:01:39
 *********************************************/

#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
typedef long long LL;
const int inf = 1 << 30;
const LL INF = 1LL << 60;
const int MaxN = 200005;

int n;
map <LL, int> cnt;
LL a[MaxN + 5];

int main()
{
	while(scanf("%d",&n) != EOF)
	{
		LL sum = 0,ans = 0;
		for(int i = 1;i <= n;i++) scanf("%lld",&a[i]);
		for(int i = 1;i <= n;i++){
			sum += a[i];
			if(sum == 0) ans++;
			ans += cnt[sum];
			cnt[sum]++;
		}
		printf("%lld\n", ans);
	}
}


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

int main(){
  int x,n;
  std::cin >> x>> n;


  std::map<int, int> m;
  rep(i,n){
    int temp;
    std::cin >> temp;
    m[temp]++;
  }

  int mi=1000;
  int ans=1000;
  for (int i = -1 ; i <= 101; i++) {
    if(m[i]==0){
      if(mi>abs(x-i)){
        // std::cout << i << ':';

        mi=min(mi,abs(x-i));
        
        ans=i;
      }

    }
  }

  std::cout << ans << '\n';

  return 0;
}


Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll, ll>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
const ll INF = 1e18;
#define pu push
#define pb push_back
#define mp make_pair
#define print(x) cout << (x) << endl;
#define rep(i,n) for(ll i = 0; i < (n); i++)
#define SORT(x) sort(x.begin(),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
#define fi first
#define sc second

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    int X;
    cin >> X;
    int num500 = X/500;
    int num5 = (X-num500*500)/5;
    cout << num500*1000+num5*5 << endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void){
	int num;
	scanf("%d", &num);

	int brick[num];
	for(int i=0; i<num; i++) {
		scanf("%d", &brick[i]);
	}

	int Break = 1;
	for(int i=0; i<num; i++) {
		if(brick[i] == Break){
			Break++;
		}
	}

	if(Break == 1) Break = num + 2;

	printf("%d\n", num-Break+1);

	return 0;
}

Measured memory_bytes: 2456