akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <ctime>
#include <cstring>
#include <functional>
#include <iostream>
#include <iomanip>
#include <limits>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <regex>
#include <vector>

#define fix(n)          cout<<fixed<<setprecision(n)
#define rep(i,n)        for (int i = 0; i < (n); ++i)
#define all(a)          (a).begin(), (a).end()
#define sort(a)         sort(all(a))
#define uniq(a)         sort(a);(a).erase(unique(all(a)), (a).end())
#define reverse(a)      reverse(all(a))
#define ctos(c)         string(1, (c))
#define out(d)          cout << (d)
#define outl(d)         std::cout<<(d)<<"\n"
#define YES()           cout << "YES" << endl
#define NO()            cout << "NO" << endl
#define Yes()           cout << "Yes" << endl
#define No()            cout << "No" << endl
#define ceil(x, y)      ((x + y - 1) / (y))
#define debug(x)        cerr << #x << ": " << (x) << '\n'
#define debug2(x, y)    cerr << #x << ": " << (x) << ", " << #y << ": " << (y) << '\n'
#define debug3(x, y, z) cerr << #x << ": " << (x) << ", " << #y << ": " << (y) << ", " << #z << ": " << (z) << '\n'
#define dbg(v)          for (size_t _ = 0; _ < v.size(); ++_){ cerr << #v << "[" << _ << "] : " << v[_] << '\n'; }
#define pb              push_back
#define fst             first
#define int             long long
#define INF             __LONG_LONG_MAX__

using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll,ll>;

const ll MOD = 1000000007; // 10^9 + 7
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

priority_queue<ll> pq;
const ll MAX = 1000000000;

void dfs(ll n, ll f) {
  if (n > MAX) return;
  // debug2(n, f);
  if (f == 7) pq.push(-n);
  dfs(n * 10 + 3, f | 0b100);
  dfs(n * 10 + 5, f | 0b010);
  dfs(n * 10 + 7, f | 0b001);
}

void solve() {
  ll n; cin >> n;
  dfs(0, 0);
  ll cnt = 0;
  while (!pq.empty() && -pq.top() <= n) {
    cnt++;
    // debug2(cnt, -pq.top());
    pq.pop();
  }
  outl(cnt);
}

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  srand((unsigned)time(NULL));
  fix(12);

  solve();
}


Measured memory_bytes: 768
#include <iostream>

using namespace std;

int main() {
  int n;
  cin >> n;
  bool flag = false;
  do {
    if (n%10 == 7) {
      flag = true;
      break;
    }
    n /= 10;
  }
  while (n != 0);
    if (flag) cout << "Yes";
  	else cout << "No";
}

Measured memory_bytes: 3128
package main

import "fmt"

func main() {
	var w, a, b int
	fmt.Scan(&w, &a, &b)

	if b < a-w {
		fmt.Println(a - b - w)
	} else if a-w <= b && b <= a+w {
		fmt.Println(0)
	} else {
		fmt.Println(b - a - w)
	}
}


Measured memory_bytes: 512
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<deque>
#include<queue>
#include<stack>
#include<utility>

using namespace std;

#define SPEEDY cin.tie(0);ios::sync_with_stdio(false);

#define REP(i,n) for(int i=0;i<(n);i++)
#define ARREP(i,n,X) for(int i=0;i<(n);i++)cin>>X[i]
#define FOR(i,X,n) for(int i=(X);i<(n);i++)
#define EREP(i,n) for(int i=1;i<=n;i++)

#define DEB(X) if(mode==1)cout<< #X <<": "<<X<<" ";
#define DEB2(X) if(mode==1)cout<< X <<" ";
#define ARDEB(i,X) if(mode==1)cout<< #X <<"["<<i<<"]: "<<X[i]<<" ";
#define FORDEB(n,X) if(mode==1)for(int i=0;i<(n);i++)ARDEB(i,X)
#define END if(mode==1)cout<<endl;

typedef long long int ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
#define ALL(X) X.begin(),X.end()
struct edge{int to,cost;};
//struct edge{int from,cost,to;};

const int INF=100000000;
int mode=1;

int main(){
	int n,m;
	cin>>n>>m;
	cout<<(n-1)*(m-1)<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define INF 1e18
#define int long long
#define Rep(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) Rep(i, 0, n)
#define all(a) (a).begin(), (a).end()
using namespace std;
typedef pair<int, int> P;
typedef pair<int, P> PP;
const int mod = 1000000007;

int h, w;
int dy[] = {0, -1, 0, 1}, dx[] = {1, 0, -1, 0};
bool in(int y, int x) { return 0 <= y && y < h && 0 <= x && x < w; }

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

    cin >> h >> w;
    vector<string> s(h);
    rep(i, h) cin >> s[i];
    bool f = true;
    rep(i, h)
    {
        rep(j, w)
        {
            if (s[i][j] == '.')
                continue;
            bool g = false;
            rep(k, 4)
            {
                int ny = i + dy[k], nx = j + dx[k];
                if (in(ny, nx) && s[ny][nx] == '#')
                    g = true;
            }
            f &= g;
        }
    }
    cout << (f ? "Yes" : "No") << endl;
}

Measured memory_bytes: 256
package main

import "fmt"

func main() {
	var s int
	fmt.Scan(&s)

	l := make(map[int]int, 1000000)
	ans := 0
	for a := s; ; a = f(a) {
		ans++
		if _, ok := l[a]; ok {
			break
		}
		l[a]++
	}
	fmt.Println(ans)
}

func f(n int) int {
	if n%2 == 1 {
		return 3*n + 1
	}
	return n / 2
}


Measured memory_bytes: 36608
def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]

s,t=s1()
a,b=n1()
u=s0()
if s==u:
    a=a-1
else:
    b=b-1
print(a,b)

Measured memory_bytes: 3064
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<queue>
#include<stack>
#include<cmath>

using namespace std;

int main() {
	int N;
	cin >> N;
	int nowT = 0;
	int nowX = 0, nowY = 0;
	for (int i = 0; i < N; ++i) {
		int t;
		int x, y;
		cin >> t >> x >> y;

		if (t - nowT < abs(x + y - nowX - nowY)) {
			cout << "No" << endl;
			return 0;
		}
		else if(t - nowT == abs(x + y - nowX - nowY)){
			//pass;
		}
		else if ((t - nowT) % 2 != abs(x + y - nowX - nowY) % 2) {
			cout << "No" << endl;
			return 0;
		}
		else {
			//pass;
		}
		nowX = x;
		nowY = y;
		nowT = t;
	}
	cout << "Yes" << endl;
	return 0;
}

Measured memory_bytes: 256
#pragma once
#include <stdio.h>
#include <sstream>
#include <string.h>
#include <vector>
#include <map>
#include <algorithm>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <deque>
#include <limits>
#include <iomanip>
#include <ctype.h>
#define _USE_MATH_DEFINES
#include <iostream>
#include <math.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define bit(x,v) ((ll)x << v)

const ll INF = 1000000007;
const int MAX = 210000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}

// 二項係数計算
long long COM(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}
int pr[100010];
void uini(int n) {
	for (size_t i = 0; i <= n; i++)
	{
		pr[i] = i;
	}
}

int parent(int x) {
	if (x == pr[x]) return x;
	return pr[x] = parent(pr[x]);
}

bool unit(int x, int y) {
	int px = parent(x);
	int py = parent(y);

	if (px == py) return false;
	if (px < py) {
		pr[py] = px;
	}
	else {
		pr[px] = py;
	}
	return true;
}

ll bit[200010];
int max_n = 200000;
int pm = 0;
void add(int x) {

	while (max_n >= x)
	{
		bit[x]++;
		x += x & -x;
	}
}
void sub(int x) {
	while (max_n >= x)
	{
		bit[x]--;
		x += x & -x;
	}
}
int search(int x) {

	int k = 0;
	int p = 1;
	while (p * 2 <= max_n)
	{
		p *= 2;
	}
	for (int i = p; i > 0; i /= 2)
	{
		if (i + k < max_n && bit[i + k] < x) {
			x -= bit[i + k];
			k += i;
		}
	}
	return k + 1;
}
void solv() {
	int n;
	cin >> n;
	int a[110];
	for (size_t i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	int p = 0;
	while (true)
	{
		bool ok = true;
		for (size_t i = 1; i < n; i++)
		{
			if (a[i - 1] > a[i]) {
				swap(a[i - 1], a[i]);
				ok = false;
				p++;
			}
		}
		if (ok) break;
	}

	for (size_t i = 0; i < n; i++)
	{
		if (i > 0) cout << " ";
		cout << a[i];
	}
	cout << endl;
	cout << p << endl;
}
int main() {
	//	COMinit();
	solv();
	return 0;
}



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

struct task {
    int A, B;
    bool operator<(const task& r) const {
        return B < r.B;
    }
};

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

    vector<task> v;
    for (int i=0; i<N; i++) {
        int a,b; cin >> a >> b;
        task t = {a, b};
        v.push_back(t);
    }
    sort(v.begin(), v.end());

    bool ok = true;
    int t = 0;
    for (int i=0; i<v.size(); i++) {

        if (t <= v[i].B - v[i].A) {
            t += v[i].A;
        } else {
            ok = false;
            break;
        }
    }

    cout << (ok ? "Yes": "No") << endl;

    return 0;
}

Measured memory_bytes: 2420
// {{{
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <complex>
#include <vector>
#include <list>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <algorithm>
#if __cplusplus >= 201103
#include <numeric>
#endif
using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define FORR(i, a, b) for(int i = (a); i >= (b); i--)
#define REP(i, n) for(int i = 0; i < (n); i++)
#define REPR(i, n) for(int i = (n); i >= 0; i--)
#define ALL(x) (x).begin(), (x).end()

//#if __cplusplus >= 201103
typedef long long ll;
//#endif
typedef pair<int, int> P;
typedef pair<int, P> IP;

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

const int INF = 100000000;
//#if __cplusplus >= 201103
const ll LINF = 10000000000000000ll;
//#endif
const int MOD = 1e9 + 7;
const double EPS = 1e-9;
// }}}

int n;
vector<int> v;

void init()
{
}

void solve()
{
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n;
    int par = 0;
    REP(i, n){
        int val;
        cin >> val;
        v.push_back(val);
        if(val % 2 != 0) par = (par + 1) % 2;
    }
    cout << (par == 0 ? "YES" : "NO") << endl;
    return 0;
}

// vim:set foldmethod=marker:


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

int main(){
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    int taka = (c + b - 1) / b;
    int aok = (a + d - 1) / d;
    string ans = "Yes";
    if(taka > aok) ans = "No";
    cout << ans << endl;
}

Measured memory_bytes: 3624
import math
N=int(input())
x=[0]*N
y=[0]*N
for i in range(N):
    x[i], y[i]=map(int, input().split())
sum=0
for i in range(N):
    for j in range(N):
        sum+=math.sqrt((x[i]-x[j])**2+(y[i]-y[j])**2)
print(sum/N)

Measured memory_bytes: 3064
# include "bits/stdc++.h"
using namespace std;
using LL = long long;
using ULL = unsigned long long;
const double PI = acos(-1);
template<class T>constexpr T INF() { return ::std::numeric_limits<T>::max(); }
template<class T>constexpr T HINF() { return INF<T>() / 2; }
template <typename T_char>T_char TL(T_char cX) { return tolower(cX); };
template <typename T_char>T_char TU(T_char cX) { return toupper(cX); };
typedef pair<LL, LL> pii;
const int vy[] = { -1, -1, -1, 0, 1, 1, 1, 0 }, vx[] = { -1, 0, 1, 1, 1, 0, -1, -1 };
const int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 };
int popcnt(unsigned long long n) { int cnt = 0; for (int i = 0; i < 64; i++)if ((n >> i) & 1)cnt++; return cnt; }
int d_sum(LL n) { int ret = 0; while (n > 0) { ret += n % 10; n /= 10; }return ret; }
int d_cnt(LL n) { int ret = 0; while (n > 0) { ret++; n /= 10; }return ret; }
LL gcd(LL a, LL b) { if (b == 0)return a; return gcd(b, a%b); };
LL lcm(LL a, LL b) { LL g = gcd(a, b); return a / g*b; };
# define ALL(qpqpq)           (qpqpq).begin(),(qpqpq).end()
# define UNIQUE(wpwpw)        sort(ALL((wpwpw)));(wpwpw).erase(unique(ALL((wpwpw))),(wpwpw).end())
# define LOWER(epepe)         transform(ALL((epepe)),(epepe).begin(),TL<char>)
# define UPPER(rprpr)         transform(ALL((rprpr)),(rprpr).begin(),TU<char>)
# define FOR(i,tptpt,ypypy)   for(LL i=(tptpt);i<(ypypy);i++)
# define REP(i,upupu)         FOR(i,0,upupu)
# define INIT                 std::ios::sync_with_stdio(false);std::cin.tie(0)

int h, w, n;
int sx, sy;
string s, t;

int main(){
    cin >> h >> w >> n;
    cin >> sy >> sx;
    sy--, sx--;
    cin >> s >> t;
    int l = 0, r = w, u = 0, d = h;
    if (s[n-1] == 'L') ++l;
    if (s[n-1] == 'R') --r;
    if (s[n-1] == 'U') ++u;
    if (s[n-1] == 'D') --d;
    for (int i = n-2; i >= 0; --i) {
        if (t[i] == 'L') r = min(r + 1, w);
        if (t[i] == 'R') l = max(0, l - 1);
        if (s[i] == 'L') l = l + 1;
        if (s[i] == 'R') r = r - 1;
        if (t[i] == 'U') d = min(d + 1, h);
        if (t[i] == 'D') u = max(0, u - 1);
        if (s[i] == 'U') u = u + 1;
        if (s[i] == 'D') d = d - 1; 
        if (l >= r || u >= d){
            cout << "NO" << endl;
            return 0;
        }
    }
    if (sx < l || sx >= r || sy < u || sy >= d){
        cout << "NO" << endl;
    }else{
        cout << "YES" << endl;
    }
}

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

const int N = 1e4;
int n;
int a[N + 7];
int b[N + 7];

void fail() {
  cout << "No" << endl;
  exit(0);
}

int main() {
  ios_base::sync_with_stdio(0);
  cin >> n;
  long long sa = 0;
  long long sb = 0;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    sa += a[i];
  }
  for (int i = 1; i <= n; ++i) {
    cin >> b[i];
    sb += b[i];
  }
  
  if (sa > sb) fail();
  long long ile = sb - sa;

  long long pot = 0;
  for (int i = 1; i <= n; ++i) {
    if (a[i] < b[i]) {
      int roz = b[i] - a[i];
      pot += (roz + 1) / 2;
    }
  }  
  
  if (pot > ile) fail();
  
  cout << "Yes" << endl;
  return 0;
}

Measured memory_bytes: 384
N, M = map(int, input().split())
conflicts = [list(map(int, input().split())) for i in range(M)]

intervals = []
for conflict in conflicts:
    intervals.append([conflict[0], conflict[1]-1])

intervals = sorted(intervals, key=lambda x: x[1])#interval[1]の大きい順にソート

count = 0
end = -float("inf")
for interval in intervals:
    if interval[0] > end:
        count += 1
        end = interval[1]

print(count)

Measured memory_bytes: 41328
#include <iostream>
using namespace std;
int main(){
int a[3];
int emp;
cin>>a[0]>>a[1]>>a[2];
for(int i=0;i<3;i++){
for(int j=i;j<3;j++){
if(a[i]>a[j]){emp=a[i];a[i]=a[j];a[j]=emp;}
}
}
cout<<a[0]<<" "<<a[1]<<" "<<a[2]<<endl;
return 0;
}

Measured memory_bytes: 3088
#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 sz(x) (ll)(x).size()
#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define eb emplace_back

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

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

// LowLink
template<typename G>
struct LowLink {
  const G &g;
  vector<int> used, ord, low;
  vector<int> articulation;
  vector<pair<int, int>> bridge;

  LowLink(const G &g) : g(g) {}

  int dfs(int idx, int k, int par) {
    used[idx] = true;
    ord[idx] = k++;
    low[idx] = ord[idx];
    bool is_articulation = false;
    int cnt = 0;
    for(auto &to : g[idx]) {
      if(!used[to]) {
        ++cnt;
        k = dfs(to, k, idx);
        low[idx] = min(low[idx], low[to]);
        is_articulation |= ~par && low[to] >= ord[idx];
        if(ord[idx] < low[to]) bridge.emplace_back(minmax(idx, (int) to));
      } else if(to != par) {
        low[idx] = min(low[idx], ord[to]);
      }
    }
    is_articulation |= par == -1 && cnt > 1;
    if(is_articulation) articulation.push_back(idx);
    return k;
  }

  virtual void build() {
    used.assign(g.size(), 0);
    ord.assign(g.size(), 0);
    low.assign(g.size(), 0);
    int k = 0;
    for(int i = 0; i < g.size(); i++) {
      if(!used[i]) k = dfs(i, k, -1);
    }
  }
};

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

  ll n,m;
  cin >> n >> m;
  vector<vector<ll>> g(n);
  rep(i,m) {
    ll s,t;
    cin >> s >> t;
    g[s].push_back(t);
    g[t].push_back(s);
  }
  LowLink<vector<vector<ll>>> t(g);
  t.build();

  vector<int> ans = t.articulation; // copy
  sort(all(ans));
  for (ll v : ans) {
    cout << v << endl;
  }
}



Measured memory_bytes: 5284
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using Graph=vector<vector<int>>;
#define MOD 1000000007

int main(){
  int N;
  cin>>N;
  for(int i=0;i<N;i++){
    cout<<"ACL";
  }
  cout<<endl;
}


Measured memory_bytes: 3520
#include <bits/stdc++.h>
using namespace std;
#define INF 1<<30
#define endl '\n'
#define maxn 100005
#define tc printf("Case %d: ", cs)
#define tcn printf("Case %d:\n", cs);
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
typedef long long ll;
const double PI = acos(-1.0);

#define dbg1(x) cerr << #x << " = " << x << endl;
#define dbg2(x, y) cerr << #x << " = " << x << ", " << #y << " = " << y << endl;
#define dbg3(x, y, z) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;
#define dbg4(w,x, y, z) cerr << #w << " = " << w << ", " <<#x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;

template < typename F, typename S >
ostream& operator << ( ostream& os, const pair< F, S > & p ) {
	return os << "(" << p.first << ", " << p.second << ")";
}

template < typename T >
ostream &operator << ( ostream & os, const vector< T > &v ) {
	os << "{";
	for (auto it = v.begin(); it != v.end(); ++it) {
		if ( it != v.begin() ) os << ", ";
		os << *it;
	}
	return os << "}";
}

template < typename T >
ostream &operator << ( ostream & os, const set< T > &v ) {
	os << "[";
	for (auto it = v.begin(); it != v.end(); ++it) {
		if ( it != v.begin()) os << ", ";
		os << *it;
	}
	return os << "]";
}

template < typename F, typename S >
ostream &operator << ( ostream & os, const map< F, S > &v ) {
	os << "[";
	for (auto it = v.begin(); it != v.end(); ++it) {
		if ( it != v.begin() ) os << ", ";
		os << it -> first << " = " << it -> second ;
	}
	return os << "]";
}

#define dbg(args...) do {cerr << #args << " : "; faltu(args); } while(0)

clock_t tStart = clock();
#define timeStamp dbg("Execution Time: ", (double)(clock() - tStart)/CLOCKS_PER_SEC)

void faltu () { cerr << endl; }

template <typename T>
void faltu( T a[], int n ) {
	for (int i = 0; i < n; ++i) cerr << a[i] << ' ';
	cerr << endl;
}

template <typename T, typename ... hello>
void faltu( T arg, const hello &... rest) { cerr << arg << ' '; faltu(rest...); }
// Program showing a policy-based data structure.
#include <ext/pb_ds/assoc_container.hpp> // Common file 
#include <ext/pb_ds/tree_policy.hpp>
#include <functional> // for less 
#include <iostream>
using namespace __gnu_pbds;
using namespace std;
// GNU link : https://goo.gl/WVDL6g
typedef tree<int, null_type, less_equal<int>, rb_tree_tag,
        tree_order_statistics_node_update>
        new_data_set;

/**___________________________________________________**/



int main()
{
	FASTIO
	/*
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	freopen("error.txt", "w", stderr);
#endif
//*/

	map<int, bool> possible;
	possible[0] = true;
	for (int i = 100; i < 106; i++) {
		for (int j = i; j < 100006; j++) {
			possible[j] |= possible[j - i];
		}
	}
	int n;
	cin >> n;
	cout << possible[n] << endl;
}

Measured memory_bytes: 4992
# n個の点全てを含む円のうち半径が最小である円の
# 中心座標と半径を求める
class SolvCircle

    LOOP_MAX = 1000

    # 移動距離がこの値以下になったら処理を終了させる
    CONVRGV = 1.0e-16

    #
    #=== 円の中心座標と半径を求める
    #
    #_pt_x_ :: n個の点のx座標の配列
    #_pt_y_ :: n個の点のy座標の配列
    # 
    #返り値::配列を返す。[中心点のx座標, 中心点のy座標, 円の半径]
    #
    def solv_circle(pt_x, pt_y)
        mv_rate  = 0.5 # 移動係数
        max_dist = 0.0 # 中心点から最遠点までの距離
        cx       = 0.0 # 中心点のx座標。最初は仮に0とし、更新していく。
        cy       = 0.0 # 中心点のy座標。最初は仮に0とし、更新していく。
        k        = 0
        cvgflg   = false

        while (cvgflg == false)

            LOOP_MAX.times { |t|
                # 仮中心点からの最遠点を求める
                max_dist = 0.0
                pt_x.length.times { |i|
                    dist = distance(cx, cy, pt_x[i], pt_y[i])
                    if (dist > max_dist)
                        max_dist = dist
                        k        = i
                    end
                }

                # mv_rateに応じて、仮中心点を更新する移動距離を求める。
                dx = (pt_x[k] - cx) * mv_rate
                dy =  (pt_y[k] - cy) * mv_rate
                dist = Math.sqrt(dx ** 2 + dy **2 )
                
                # 仮中心点を更新する。
                cx += dx
                cy += dy

                # 移動距離が境界値を下回っていればループを抜ける
                if (dist <= CONVRGV)
                    cvgflg = true
                    break
                end
            }

            mv_rate /= 2.0 # 移動係数が1.5を下回ってくるとTLEとなりやすい。
        end

        return [cx, cy, max_dist]
    end

    #
    #=== 二点の距離を求める
    #
    def distance(x1, y1, x2, y2)
        dx = x2 - x1
        dy = y2 - y1
        Math.sqrt(dx * dx + dy * dy)
    end
end

N = gets.to_i
x = Array.new(N)
y = Array.new(N)
N.times{|i| x[i],y[i] = gets.split.map(&:to_i)}

sc = SolvCircle.new
ans = sc.solv_circle(x, y)
puts ans[2]



Measured memory_bytes: 1916
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define INF 1e12

#define PB push_back
#define PF push_front
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vpi vector<pii>
#define vll vector<ll>
#define vpl vector<pll>
#define vvi vector<vector<int>>
#define vvl vector<vector<ll>>
#define MX(x) *max_element(all(x))
#define MN(x) *min_element(all(x))
#define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pr_d(x) cout << fixed << setprecision(15) << x << endl
#define ud(c, x) distance(c.begin(), upper_bound(all(c), x))
#define ld(c, x) distance(c.begin(), lower_bound(all(c), x))
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i, a, b) for (int i = (a); i < (b); ++i)
#define rep3(i, n) for (int i = (n - 1); i >= 0; --i)
#define rep4(i, a, b) for (int i = (a); i > (b); --i)
#define pb push_back
#define out(x) cout << x << "\n"
bool odd(int i) { return i % 2; }

#define all(v) v.begin(), v.end()
#define size(x) int(x.size())

int gcd(int a, int b) { return __gcd(a, b); }
int lcm(int a, int b) { return a * (b / gcd(a, b)); }
void Yes_No(bool f) {
  if (f)
    printf("Yes\n");
  else
    printf("No\n");
}

void deb_p(pii p) { printf("pair = %d %d\n", p.fi, p.se); }
void deb_i(int i) { printf("i = %d\n", i); }
void deb_v(vector<int> v) {
  printf("v = ");
  for (auto i : v) printf("%d ", i);
  printf("\n");
}
template <typename T>
bool chmax(T& a, const T& b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <typename T>
bool chmin(T& a, const T& b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
//-------------------ここから回答する-----------------------

void solve(void) {
  int x, a, b;
  cin >> x >> a >> b;
  if (abs(x - a) < abs(x - b))
    out('A');
  else
    out('B');
}
int main(void) { solve(); }


Measured memory_bytes: 3616
#include <iostream>
#include <string>
#define rep(i, n) for(unsigned int i = 0; i < (unsigned int)(n); i++)
using namespace std;

int main(){
  string str;
  cin >> str;
  int count = 0;

  rep(i, str.size()){
    if(str[i] == 'A'){
      count++;
    }
  }

  if(count == 0 || count == 3){
    cout << "No" << endl;
  }else{
    cout << "Yes" << endl;
  }
}

Measured memory_bytes: 256
from collections import deque

N, M = map(int, input().split())
A, B = (
    zip(*(map(int, input().split()) for _ in range(M))) if M else
    ((), ())
)
S, T = map(int, input().split())

G = [set() for _ in range(N + 1)]
for x, y in zip(A, B):
    G[x].add(y)

INF = 10**10

dp = [[INF for j in range(3)] for i in range(N + 1)]

q = deque()
q.append((S, 0))
dp[S][0] = 0

while q:
    i, k = q.popleft()
    L = (k + 1) % 3
    for x in G[i]:
        if dp[x][L] == INF:
            dp[x][L] = dp[i][k] + (k + 1) // 3
            q.append((x, L))

ans = (
    -1 if dp[T][0] == INF else
    dp[T][0]
)

print(ans)


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

int main() {
  int n;
  cin >> n;
  string ans = "";
  while(n != 0){
    int t = n%(-2);
    if(t == -1) t = 1;
    ans.push_back('0'+t);
    n = (n-t)/(-2);
  }
  if(ans.size() == 0) ans = "0";
  reverse(ans.begin(),ans.end());
  cout << ans << endl;
}


Measured memory_bytes: 3624
#include <bits/stdc++.h>
#include<stdlib.h>
#include<math.h>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ll long long
#define INF 2000000000
#define Min(a,b) (a<b?a:b)
#define Max(a,b) (a>b?a:b)
#define PI 3.1415926535897932
using namespace std;






int main()
{
int a,b,c,d,e;
cin>>a>>b>>c>>d>>e;
cout<<15-(a+b+c+d+e);
return 0;

}



Measured memory_bytes: 3592
# describe Abc134A do
#   context 'test' do
#     it 'sample' do
#       expect(Abc134A.calc(4)).to be(48)
#       expect(Abc134A.calc(15)).to be(675)
#       expect(Abc134A.calc(80)).to be(19200)
#     end
#   end
# end

class Abc134A
  def self.input()
    password_string = STDIN.gets.to_i
  end

  def self.output(result)
    puts result
  end

  def self.calc(r)
    3 * r * r
  end

  def self.main()
    r = input()
    result = calc(r)
    output(result)
  end
end

if __FILE__ == $0
  Abc134A.main
  exit
end

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

int main()
{
    int x,y,z,i,j,k;
    int n;
    cin>>x>>n;
    int p[n];
    bool b[101]={false};
    int mx=0;
    for(i=0;i<n;i++)
    {
        cin>>p[i];
        b[p[i]]=true;
    }
    int mn=INT_MAX;
    int index;
    for(i=0;i<=1000;i++)
    {
        if(b[i]==false && max(x-i,i-x)<mn)
        {
            mn=max(x-i,i-x);
            index=i;
        }
    }
    cout<<index<<endl;
    
	return 0;
}


Measured memory_bytes: 3668
#!/usr/bin/env pypy3
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

import itertools

def main():
    mod=10**9+7
    N,M,R=MI()
    r=LI()
    inf=10**10
    d=[[inf]*N for _ in range(N)]
    for _ in range(M):
        a,b,c=MI()
        a-=1
        b-=1
        d[a][b]=c
        d[b][a]=c
    for i in range(N):
        d[i][i]=0
        
    def warshall_floyd(d):
        #d[i][j]: iからjへの最短距離
        for k in range(N):
            for i in range(N):
                for j in range(N):
                    d[i][j] = min(d[i][j],d[i][k] + d[k][j])
        return d
        
    d=warshall_floyd(d)
    
    ans=inf
    for ite in itertools.permutations(range(R), R):
        temp=0
        for i in range(R-1):
            a=r[ite[i]]-1
            b=r[ite[i+1]]-1
            temp+=d[a][b]
        ans=min(ans,temp)
        
    print(ans)
            
        
        
    
    
    

main()


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

int main(){
  int a, b, c;
  cin >> a >> b >> c;
  if(a == b && b == c) cout << "No" << endl;
  else if(a == b || b == c || c == a) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 256
import java.util.*

fun main(args : Array<String>) {
    val sc = Scanner(System.`in`)
    val w = sc.next().toLong()
    val a = sc.next().toLong()
    val b = sc.next().toLong()
    println(problem56b(w, a, b))
}

fun problem56b(w: Long, a: Long, b: Long): Long {
    val aRight = a + w
    val bRight = b + w
    return when {
        aRight < b -> b - aRight
        bRight < a -> a - bRight
        else -> 0
    }
}

Measured memory_bytes: 29344
n=int(input())
h=list(map(int,input().split()))
ans='Yes'
for i in range(n-1):
  if h[i]<h[i+1]:
    h[i+1]-=1
for i in range(n-1):
  if h[i]>h[i+1]:
    ans='No'
print(ans)

Measured memory_bytes: 20736
N = int(input())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7

sums = 0
for a in A:
    sums += a
    sums %= mod

ans = 0

for a in A:
    sums = (sums - a) % mod
    ansi = (sums * a) % mod
    ans += ansi
    ans %= mod

print(ans)


Measured memory_bytes: 31536
#include <vector>
#include <list>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <utility>
#include <functional>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <cassert>
using namespace std;
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
const double EPS = 1e-10;
const double PI  = acos(-1.0);

int main(){
	int n;
	cin>>n;
	vi s(n),l(n),p(n);
	REP(i,n){
		cin>>s[i]>>l[i]>>p[i];
	}
	int m;
	cin>>m;
	vi w(m);
	REP(i,m){
		cin>>w[i];
	}
	vvi dp(n+1,vi(400+1));
	REP(i,n){
		vi available(400+1);
		for(int rep=1;s[i]*rep<=400;rep++){
			FOR(k,s[i]*rep,min(l[i]*rep,400)+1){
				available[k]=max(available[k],rep);
			}
		}
		REP(k,400+1){
			if(available[k]){
				REP(j,400+1){
					if(j-k>=0){
						dp[i+1][j]=max(dp[i+1][j],dp[i][j-k]+p[i]*available[k]);
					}
					dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
				}
			}
		}
	}
	vi ans(m);
	bool flag=false;
	REP(melody,m){
		ans[melody]=dp[n][w[melody]];
		if(ans[melody]==0){
			flag=true;
		}
	}
	if(flag){
		cout<<-1<<endl;
	}else{
		REP(i,m){
			cout<<ans[i]<<endl;
		}
	}

}

Measured memory_bytes: 1800
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc=new Scanner(System.in);
    String str=sc.next();
    sc.close();
    int start=0,end=0;
    for(int i=0;i<str.length();i++){
      if(str.charAt(i)=='A'){
        start=i;
        break;
      }
    }
    for(int i=str.length()-1;i>=0;i--){
      if(str.charAt(i)=='Z'){
        end=i;
        break;
      }
    }
    System.out.println(end-start+1);
  }
}

Measured memory_bytes: 26500
#include <iostream>
using namespace std;
int main(){
    int a,b;
    cin >> a;
    cin >> b;
    if(a<b){
        cout << "a < b\n";
    }
    else if(a>b){
        cout << "a > b\n";
    }
    else if(a==b){
        cout << "a == b\n";
    }
}

Measured memory_bytes: 3076
#include <iostream>
#include <iomanip>

using namespace std;

int N;
double a[100];
double s;

int main(){
    cin >> N;
    for(int i=0;i<N;i++) cin >> a[i];
    s = 1;
    for(int i=0;i<N;i++){
        s *= a[i];
    }
    double sum = 0;
    for(int i=0;i<N;i++){
        sum += s / a[i];
    }
    double d = (double)s / (double)sum;
    cout << setprecision(30) << d << endl; 
    return 0;
}

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

namespace atcorder2
{
    class Program
    {
        public static long Read()
        {
            return long.Parse(Console.ReadLine());
        }

        public static long[] Reads()
        {

            return Console.ReadLine().Split().Select(long.Parse).ToArray();
        }

        public static long d(long sx,long sy,long gx,long gy)
        {
            return Math.Abs(gx - sx) + Math.Abs(gy - sy);
        }
      



        static void Main(string[] args)
        {
            var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);

            var n = Read();
            var a = Reads();
            var data = new Dictionary<long, long>();
            for (int i = 0; i < n; i++)
            {
                if (data.ContainsKey(a[i]))             
                    data[a[i]]++;
                else
                    data.Add(a[i], 1);
            }
            long ans = 0;
            foreach(KeyValuePair<long,long> s in data)
            {
                if (s.Key > s.Value)
                    ans += s.Value;
                else if (s.Key < s.Value)
                    ans += (s.Value - s.Key);   
            }
            Console.WriteLine(ans);
             

            Console.Out.Flush();
        }
    }
}




Measured memory_bytes: 29152
from collections import deque
N, M = map(int, input().split())
node_dic = {}

for i in range(3 * N):
    node_dic[i] = []

for _ in range(M):
    u, v = map(int, input().split())
    node_dic[(u - 1) * 3].append((v - 1) * 3 + 1)
    node_dic[(u - 1) * 3 + 1].append((v - 1) * 3 + 2)
    node_dic[(u - 1) * 3 + 2].append((v - 1) * 3)

S, T = map(int, input().split())

ans_array = [-1] * (3 * N)
use_array = [0] * (3 * N)

edge_queue = deque()
ans_array[(S-1)*3] = 0
use_array[(S-1)*3] = 1
edge_queue.append((S-1)*3)
while(len(edge_queue)):
    edge = edge_queue.popleft()
    value = ans_array[edge]
    for e in node_dic[edge]:
        if not use_array[e]:
            edge_queue.append(e)
            ans_array[e] = value + 1
            use_array[e] = 1

print(ans_array[(T-1)*3]//3)



Measured memory_bytes: 81956
using System;
using System.Linq;

namespace abc058_a
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] x = Console.ReadLine().Split().Select(int.Parse).ToArray();
            Console.WriteLine(x[0] - x[1] == x[1] - x[2] ? "YES" : "NO");
        }
    }
}

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

int main() {
  ll t1, t2;
  ll a1, a2;
  ll b1, b2;
  cin>>t1>>t2>>a1>>a2>>b1>>b2;
  a1 *= t1; a2 *= t2;
  b1 *= t1; b2 *= t2;
  a2 += a1;
  b2 += b1;
  if (a2 == b2) {
    puts("infinity");
    return 0;
  }
  if (a2 < b2) {
    swap(a1,b1);
    swap(a2,b2);
  }
  ll d = a2-b2;
  ll c = b1-a1;
  ll ans = 0;
  if (c > 0) {
    ans = (c-1)/d+1;
    ans *= 2;
    ans--;
    if (c%d == 0) ans++;
  }
  cout << ans << endl;
  return 0;
}

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

// Shrotening
#define fst first
#define snd second
#define pb push_back

// Loop
#define FOR(i,a,b) for(long i=(a);i<(b);++i)
#define RFOR(i,a,b) for(long i=(a);i>=(b);--i)

#define REP(i,a) for(long i=0;i<(a);++i)
#define RREP(i,a) for(long i=(a);i>=0;--i)

#define EACH(i,a) for(auto (i)=(a).begin(),_END=(a).end();i!=_END;++i)
#define REACH(i,a) for(auto (i)=(a).rbegin(),_END=(a).rend();i!=_END;++i)

//Algorithm
#define ALL(a) (a).begin(), a.end()
#define RALL(a) (a).rbegin(), a.rend()
#define EXIST(a,x) ((a).find(x)!=(a).end())
#define SORT(a) std::sort((a).begin(), (a).end())
#define UNIQUE(a) std::sort((a).begin(), a.end()), a.erase(std::unique((a).begin(), a.end()), a.end());
#define SUM(a) std::accumulate((a).begin(), (a).end(), 0);

//Setting
#define OPT std::cin.tie(0);std::ios::sync_with_stdio(false);

//debug message
bool debug = true;
#define MSG(s)   if(debug){std::cout << s << std::endl;}
#define DEBUG(x) if(debug){std::cout << "debug(" << #x << "): " << x << std::endl;}

//alias
typedef long long LL;
typedef std::vector<char> VC;
typedef std::vector<int>  VI;
typedef std::vector<long> VL;
typedef std::vector<long long> VLL;

typedef std::vector< VC > VC2;
typedef std::vector< VI > VI2;
typedef std::vector< VL > VL2;
typedef std::vector< VLL > VLL2;

typedef std::pair<int,int> PII;

int R, G;
int main() {
    std::cin >> R >> G;
    std::cout << 2*G - R << std::endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n)  for (int i = 0; i < (int) (n); i++)
#define REP1(i, n) for (int i = 1; i <= (int) (n); i++)
#define all(x)     (x).begin(), (x).end()
#define SZ(x)      ((int) (x).size())
using ll = long long;

int main() {
  int n;
  cin >> n;
  vector <int> a(n);
  REP(i, n) {
	cin >> a[i];
  }
  sort(all(a));
  bool ans = true;
  REP(i, n - 1) {
	if (a[i] == a[i + 1]) {
		ans = false;
		break;
	  }
  }
  if (ans) {
	  cout << "YES" << endl;
	} else {
	  cout << "NO" << endl;
	}
  return 0;
}


Measured memory_bytes: 1024
#include <cstdio>
#include <utility>
#include <queue>
#include <vector>
using namespace std;

int main(){
	typedef pair<int,int> pii;
	
	priority_queue< pii, vector<pii>, greater<pii> > qu;
	int tr[100002];
	int i, N, L, t = 0;
	
	scanf("%d%d", &N, &L );
	for( i = 1; i <= N; i++ )	scanf("%d", tr + i );
	
	tr[0] = tr[N+1] = 0;
	for( i = 1; i <= N; i++ )
		if( tr[i] > tr[i-1] && tr[i] > tr[i+1] ){
			qu.push( pii( L - tr[i], i ) );
			tr[i] = L;
		}

	while( !qu.empty() ){
		pii p = qu.top();
		qu.pop();
		
		t = p.first;
		int s = p.second;
		tr[s] = 0;
		
		int u = tr[s-1];
		if( u != 0 && u != L  && u > tr[s-2] ){
			qu.push( pii( t + L - u, s-1 ) );
			tr[s-1] = L;
		}
		u = tr[s+1];
		if( u != 0 && u != L  && u > tr[s+2] ){
			qu.push( pii( t + L - u, s+1 ) );
			tr[s+1] = L;
		}
	}
	printf("%d\n", t );
}

Measured memory_bytes: 0
#include<iostream>
using namespace std;
typedef long long L;

bool isPrime(L num) {
    if(num == 2 || num == 3) {
        return true;
    }
    for(L i = 2; i * i <= num; ++i) {
        if(num % i == 0) {
            return false;
        }
    }
    return true;
}

int main() {
    L number;
    cin >> number;
    while(1) {
        if(isPrime(number)) {
            cout << number;
            break;
        }
        ++number;
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod=1000000007;
const int MAXN=5010;

ll n, A, B, u, v, x, y, t, a, b, ans;
ll dp[MAXN][MAXN], sum[MAXN];

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>n>>A>>B;
	if (A>B) swap(A, B);
	dp[0][0]=sum[0]=1;
	for (int i=1; i<=n; i++){
		for (int x=2; x<=A && x<=i; x++)
			dp[i][0]=(dp[i][0] + sum[i-x] - dp[i-x][B-1])%mod;
		if (i<A) dp[i][0]++;
		
		for (int j=1; j<B && j<=i; j++){
			dp[i][j]=dp[i-1][j-1];
			if (j<A+1) continue ;
			
			if (j<=A+1 || i==j){
				for (int y=A+1; y<=j; y++)
					dp[i][j]+=dp[i-y][j-y];
			}
			else if (j>A+1){
				dp[i][j]+=dp[i-1][j-1]-dp[i-2][j-2];
				dp[i][j]+=dp[i-A-1][j-A-1];
			}
			
			dp[i][j]%=mod;
		}
		if (A<=i && i<B) dp[i][i]++;
		
		for (int j=0; j<B; j++) sum[i]=(sum[i] + dp[i][j])%mod;
	}
	
	ans=1;
	for (int i=1; i<=n; i++) ans=ans*2%mod;
	ans=(ans-sum[n])%mod;
	if (ans<0) ans+=mod;
	cout<<ans<<"\n";
	
	return 0;
}


Measured memory_bytes: 120272
n,s = map(int,input().split())
a = tuple(map(int,input().split()))
MOD = 998244353

# dp[i][j]:Aをi番目まで見たときに、和がjとなるTの個数。
dp = [[0 for _ in range(s+1)] for _ in range(n+1)]
dp[0][0] = 1

for i in range(n):
  ai = a[i]
  for j in range(s+1):
    dp[i+1][j] += 2*dp[i][j] #aiを選ぶか選ばないかの2通りある。
    dp[i+1][j] %= MOD
    if j+ai <= s:
      dp[i+1][j+ai] += dp[i][j]
      dp[i+1][j+ai] %= MOD
print(dp[n][s])
#print(dp)

Measured memory_bytes: 147300
#include <stdio.h>

#define INF -10000000
/*void maxheapfy(int *,int );*/
int left(int);
int right(int);
int parent(int);
int n;
int main() {

  int i;
  int A[5000];

  

  scanf("%d",&n);
  for(i=1;i<=n;i++) scanf("%d",&A[i]);

  /*maxheapfy(A,0);*/

  for(i=1;i<=n;i++){
    printf("node %d: key = %d, ",i,A[i]);
    if(parent(i)>=1) printf("parent key = %d, ",A[parent(i)]);
    if(left(i)<=n ) printf("left key = %d, ",A[left(i)]);
    if(right(i)<=n) printf("right key = %d, ",A[right(i)]);
    printf("\n");
  }
 
  return 0;
}
/*void maxheapfy(int *A,int i)
{
  int j;
  int l;
  int r;
  int largest;
  while(1){
    l=left(i);
    r=right(i);

    if(l<=n && A[l]>A[i]) largest=l;
    else largest=i;

    if(r<=n && A[r]>A[largest]) largest=r;

    if(largest==i) break;
    j=A[largest];
    A[largest]=A[i];
    A[i]=j;


  }
}
*/
int left(int i)
{
  return 2*i;
}
int right(int i)
{
  return 2*i+1;
}
int parent(int i)
{
  return i/2;
}

Measured memory_bytes: 604
#include <iostream>
#include <string>
#include <set>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
#define Max 1000000000
int main() {
	int a, b, c;
	while (cin >> a >> b >> c) {
		if (a + b < c) {
			cout << "No" << endl;
		}
		else {
			cout << "Yes" << endl;
		}
	}
	return 0;
}

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

int main(){
	int w,h,x,y;
	cin>>w>>h>>x>>y;
	double s=(double)w*h/2.0;
	int multi=0;
	if(2*x==w&&2*y==h) multi=1;
	cout<<s<<' '<<multi<<endl;
	return 0;
}

Measured memory_bytes: 3688
n = int(input())
*A, = map(int, input().split())
MOD = 10**9 + 7
x = ((sum(A) % MOD)**2) % MOD
y = sum(a**2 % MOD for a in A) % MOD
print(((x - y) % MOD) * pow(2, MOD - 2, MOD) % MOD)


Measured memory_bytes: 31480
#include <bits/stdc++.h>
using namespace std;
long long n,k,a[100001],h[100001];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>k>>h[1];
    h[0]=1e10;
    for(int i=2;i<=n;i++)
    {
        cin>>h[i];
    a[i]=a[i-1]+abs(h[i-1]-h[i]);
       for(int j=2;j<=k;j++)
       {
           if(i-j<=0) break;
           a[i]=min(a[i-j]+abs(h[i-j]-h[i]),a[i]);
       }
    }
    cout<<a[n];
}


Measured memory_bytes: 1792
# include "bits/stdc++.h"
using namespace std;
using LL = long long;
using ULL = unsigned long long;
const double PI = acos(-1);
template<class T>constexpr T INF() { return ::std::numeric_limits<T>::max(); }
template<class T>constexpr T HINF() { return INF<T>() / 2; }
template <typename T_char>T_char TL(T_char cX) { return tolower(cX); };
template <typename T_char>T_char TU(T_char cX) { return toupper(cX); };
const int vy[] = { -1, -1, -1, 0, 1, 1, 1, 0 }, vx[] = { -1, 0, 1, 1, 1, 0, -1, -1 };
const int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 };
int popcnt(unsigned long long n) { int cnt = 0; for (int i = 0; i < 64; i++)if ((n >> i) & 1)cnt++; return cnt; }
int d_sum(LL n) { int ret = 0; while (n > 0) { ret += n % 10; n /= 10; }return ret; }
int d_cnt(LL n) { int ret = 0; while (n > 0) { ret++; n /= 10; }return ret; }
LL gcd(LL a, LL b) { if (b == 0)return a; return gcd(b, a%b); };
LL lcm(LL a, LL b) { LL g = gcd(a, b); return a / g*b; };
# define ALL(qpqpq)           (qpqpq).begin(),(qpqpq).end()
# define UNIQUE(wpwpw)        sort(ALL((wpwpw)));(wpwpw).erase(unique(ALL((wpwpw))),(wpwpw).end())
# define LOWER(epepe)         transform(ALL((epepe)),(epepe).begin(),TL<char>)
# define UPPER(rprpr)         transform(ALL((rprpr)),(rprpr).begin(),TU<char>)
# define FOR(i,tptpt,ypypy)   for(LL i=(tptpt);i<(ypypy);i++)
# define REP(i,upupu)         FOR(i,0,upupu)

struct INIT{
    INIT(){
        std::ios::sync_with_stdio(false);
        std::cin.tie(0);
        cout << fixed << setprecision(13);
    }
}INIT;

long long power(long long n, long long k, long long m) {
	if (k == 0) {
		return 1;
	}
	else if (k % 2 == 1) {
		return power(n, k - 1, m)*n%m;
	}
	else {
		long long t = power(n, k / 2, m);
		return t*t%m;
	}
}

int n;
string x;
LL houjo[202020];
const LL mod = 998244353;

LL calc(LL num){
    string s1 = x.substr(0, (int)x.size() / num);
    string s2 = s1;
    REP(i, (int)s2.size())s2[i] = (s2[i] == '1' ? '0' : '1');
    string s = "";
    REP(i, num){
        s += (i % 2 ? s2 : s1);
    }
    LL ret = 0;
    REP(i, (int)s1.size()){
        if(s1[i] == '1')(ret += power(2, (int)s1.size() - 1 - i, mod)) %= mod;
    }
    if(s <= x)ret++;
    return ret % mod;
}

int main(){
    cin >> n >> x;
    vector<int> di;
    for(int i = 1;i <= n;i += 2){
        if(n % i == 0)di.emplace_back(i);
    }
    for(int i = (int)di.size() - 1;i >= 0;i--){
        houjo[i] = calc(di[i]);
        for(int j = i + 1;j < (int)di.size();j++){
            if(di[j] % di[i] == 0){
                houjo[i] -= houjo[j];
                if(houjo[j] < 0)houjo[0] += mod;
            }
        }
    }
    LL ans = 0;
    REP(i, (int)di.size()){
        (ans += (2LL * n / di[i]) * houjo[i]) %= mod;
    }
    cout << ans << endl;
}

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

#define ll long long
#define ff first
#define ss second
typedef pair<int,int> ii;


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

    stack<ii> pile;

    ll t[n];
    ll minLeft[n];
    ll minRight[n];

    for(int i=0;i<n;i++)
    {
        cin>>t[i];
        minRight[i]=i;

        while(!pile.empty() && pile.top().ff>=t[i])
        {
            minRight[pile.top().ss]=i;
            pile.pop();
        }

        if(pile.empty())
            minLeft[i]=-1;
        else
            minLeft[i]=pile.top().ss;
        pile.push(ii(t[i],i));
    }

    while(!pile.empty())
    {
        minRight[pile.top().ss]=n;
        pile.pop();
    }
    ll answer=0;

    for(int i=0;i<n;i++)
    {
        ll nb= (minRight[i]-i)*(i-minLeft[i]);
        answer+=nb*t[i];
    }

    cout<<answer;

}


Measured memory_bytes: 6528
<?php

    $data = explode(" ", trim(fgets(STDIN)));
    $n = $data[0];
    $k = $data[1];
    $a = explode(" ", trim(fgets(STDIN)));
    sort($a);
    
    $gcm = $a[0];
    for($i=1; $i<$n; $i++){
        $x = $a[$i-1];
        $y = $a[$i];
        while($x!=0){
            $t = $x;
            $x = $y % $x;
            $y = $t;
        }
        if($gcm>$y) $gcm = $y;
    }
    if($a[0]<=$k && $k<=$a[$n-1] && ($k-$a[0])%$gcm==0) echo "POSSIBLE";
    else echo "IMPOSSIBLE";
    
?>

Measured memory_bytes: 12792