akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <cassert>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <limits>
#include <queue>
#include <vector>

using namespace std;

double sin60 = sqrt(3.) / 2.;

struct Pt {
  double x;
  double y;

  Pt operator+(const Pt& other) { return {x + other.x, y + other.y}; }
  Pt operator-(const Pt& other) { return {x - other.x, y - other.y}; }
  Pt operator/(double n) { return {x / n, y / n}; }
  Pt rotate60() { return {.5 * x - sin60 * y, sin60 * x + .5 * y}; }
};

void koch(vector<Pt>& pts, Pt src, Pt dst, int i) {
  if (!i) {
    pts.push_back(src);
  } else {
    auto step = (dst - src) / 3;
    auto p1 = src + step;
    auto p2 = p1 + step.rotate60();
    auto p3 = p1 + step;
    koch(pts, src, p1, i - 1);
    koch(pts, p1, p2, i - 1);
    koch(pts, p2, p3, i - 1);
    koch(pts, p3, dst, i - 1);
  }
}

int main() {
  int n;
  cin >> n;
  vector<Pt> buf;
  koch(buf, {0, 0}, {100, 0}, n);
  buf.push_back({100, 0});
  for (auto&& pt : buf) {
    cout << fixed << setprecision(8) << pt.x << " " << pt.y << endl;
  }
}



Measured memory_bytes: 3364
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cstdlib>
#define cinf(n,x,y) for(int i=0;i<(n);i++) cin >> x[i] >> y[i];
typedef long long int ll;
using namespace std;

int main(){
	string s; cin >>s;
	int ans=1e9;
	int Max=0;
	int cnt=0;
	for(char h='a';h<='z';h++){
		cnt=0;
		Max=0;
		for(int i=0;i<s.size();i++){
			if(s[i]==h){
				Max=max(Max,cnt);
				cnt=0;
			}
			else cnt++;
		}
		Max=max(Max,cnt);
		ans=min(ans,Max);
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <iostream>

using namespace std;

int n[5];

int cmp(const void *a, const void *b) {
	return *(int *)b - *(int *)a;
}

int main() {
	while (scanf("%d%d%d%d%d", &n[0], &n[1], &n[2], &n[3], &n[4]) != EOF) {
		qsort(n, 5, sizeof(int), cmp);
		for (int i=0; i<5; ++i) {
			printf (i ? " %d" : "%d", n[i]);
		}
		puts("");
	}
	return 0;
}

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

#define dump(x) cout << (x) << '\n'
#define Int int64_t
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
 
Int INF = 1e18;
int inf = 1e9;
Int mod = 1e9+7;

int main() {
    Int x, y, a, b, c;
    cin >> x >> y >> a >> b >> c;
    vector<Int> p(a), q(b), r(c);
    for (Int i = 0; i < a; i++) {
        cin >> p[i];
    }
    for (Int i = 0; i < b; i++) {
        cin >> q[i];
    }
    priority_queue<Int> rq;
    for (Int i = 0; i < c; i++) {
        cin >> r[i];
        rq.push(r[i]);
    }
    sort(all(p), greater<Int>());
    sort(all(q), greater<Int>());
    priority_queue<Int, vector<Int>, greater<Int>> pq;
    for (Int i = 0; i < x; i++) {
        pq.push(p[i]);
    }
    for (Int i = 0; i < y; i++) {
        pq.push(q[i]);
    }
    vector<Int> res;
    while (not rq.empty() and not pq.empty() and pq.top() < rq.top()) {
        res.push_back(rq.top());
        rq.pop();
        pq.pop();
    }
    Int ans = 0;
    for (Int i = 0; i < (Int)res.size(); i++) {
        ans += res[i];
    }
    while (not pq.empty()) {
        ans += pq.top();
        pq.pop();
    }
    dump(ans);
    return 0;
}

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

int main(){
  string s;
  cin >> s;
  cout << s.insert(4," ") << endl;
  return 0;
}


Measured memory_bytes: 256
N = int(input())
list = list(map(int,input().split()))
def gcd(a,b):
    while b:
        a,b = b,a%b
    return a

gcd_val = list[0]

for i in list[1::]:
    gcd_val = gcd(gcd_val,i)

print(gcd_val)

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

using namespace std;

typedef long long ll;

vector<vector<int>> adjlist;
vector<int> colors;
ll colorCounter[2];
bool bipartite;

void visit(int v, int c) {
  colors[v] = c;
  colorCounter[c]++;
  for (int w : adjlist[v]) {
    if (colors[w] == -1) {
      visit(w, 1 ^ c);
    } else if (colors[w] != (1 ^ c)) {
      bipartite = false;
    }
  }
}

int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  adjlist.resize(n);
  for (int i = 0; i < m; i++) {
    int a, b;
    scanf("%d %d", &a, &b);
    a--;
    b--;
    adjlist[a].push_back(b);
    adjlist[b].push_back(a);
  }

  bipartite = true;
  colors.resize(n, -1);
  visit(0, 1);

  ll maxEdges;
  if (bipartite) {
    maxEdges = colorCounter[0] * colorCounter[1];
  } else {
    maxEdges = 1LL * n * (n - 1) / 2;
  }
  cout << maxEdges - m << endl;

  return 0;
}


Measured memory_bytes: 6400
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long int ll;

ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}

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

const int INF = 1001001001;
const ll LINF = 1001002003004005006ll;

int main() {
  long n, a, b;
  cin >> n >> a >> b;
  long div = n / (a + b);
  long remain = n % (a + b);
  long plus = 0;
  if (remain >= a)  plus = a;
  else plus = remain;

  cout << div * a + plus << endl;
  return 0;
}

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

int main() {
	int s; cin >> s;
	map<int, int>a;
	a[s]++;

	int nowA = s, ans = 1;
	while (true) {

		if (nowA % 2 == 0) {
			nowA /= 2;
			a[nowA]++;
		}
		else if (nowA % 2 == 1) {
			(nowA *= 3) += 1;
			a[nowA]++;
		}
		ans++;
		if (a[nowA] == 2) {
			cout << ans << endl;
			return 0;
		}
	}

	return 0;
}

Measured memory_bytes: 256
//#include <bits/stdc++.h>
#include <complex>
#include <iostream>
#define rep(i,l,n) for(int i=l;i<n;i++)
using namespace std;
typedef complex<double> xy_t;

double cross_product(xy_t a,xy_t b){
	return (conj(a)*b).imag();
}

double x[4],y[4];

int main(){
	while(true){
		rep(i,0,4) cin>>x[i]>>y[i];
		if(!cin) break;
		xy_t a(x[0],y[0]),b(x[1],y[1]),c(x[2],y[2]),p(x[3],y[3]);
		double pab,pbc,pca;
		pab=cross_product(a-p,b-p);
		pbc=cross_product(b-p,c-p);
		pca=cross_product(c-p,a-p);
		bool ok=0;
		if((pab>0&&pbc>0&&pca>0)||(pab<0&&pbc<0&&pca<0)) ok=1;
		//bool ok=abs(pab+pbc+pca)==abs(pab)+abs(pbc)+abs(pca);
		cout<<(ok?"YES":"NO")<<endl;
	}
}

Measured memory_bytes: 1220
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int n, a, b, d1[100009], d2[100009]; vector<int> g[100009];
void dfs(int pos, int pre, int m) {
	if (pre != -1) {
		if (m == 0) d1[pos] = d1[pre] + 1;
		if (m == 1) d2[pos] = d2[pre] + 1;
	}
	for (int i : g[pos]) {
		if (i == pre) continue;
		dfs(i, pos, m);
	}
}
int main() {
	cin >> n;
	for (int i = 1; i < n; i++) {
		cin >> a >> b; a--, b--;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	dfs(0, -1, 0);
	dfs(n - 1, -1, 1);
	int c1 = 0, c2 = 0;
	for (int i = 0; i < n; i++) {
		if (d1[i] <= d2[i]) c1++;
		else c2++;
	}
	cout << (c1 > c2 ? "Fennec" : "Snuke") << endl;
	return 0;
}

Measured memory_bytes: 11136
X,N=map(int,input().split())
if N==0:
  print(X)
if N!=0:
  P=list(map(int,input().split()))
  list=[i for i in range(102)]


  for i in P:
    list[i]=-1

  sa=10**3
  ans=-1
  for i in range(len(list)):
    if abs(X-list[i])<sa:
      sa=X-list[i]
      ans=list[i]
  print(ans)    

Measured memory_bytes: 9200
#include <bits/stdc++.h>
#include <cassert>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define ok() puts(ok?"Yes":"No");
#define chmax(x,y) x = max(x,y)
#define chmin(x,y) x = min(x,y)
using namespace std;
using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using ii = pair<int, int>;
using vvi = vector<vi>;
using vii = vector<ii>;
using gt = greater<int>;
using minq = priority_queue<int, vector<int>, gt>;
using P = pair<ll,ll>;
const ll LINF = 1e18L + 1;
const int INF = 1e9 + 1;
//clang++ -std=c++11 -stdlib=libc++ 


// abc89d

int h, w, d;
int maxNum;
int a[305][305];
ll dist[100000];
map<int, P> mp;



int getDist(int before, int after) {
  int x1 = mp[before].first;
  int y1 = mp[before].second;
  int x2 = mp[after].first;
  int y2 = mp[after].second;
  return abs(x1-x2) + abs(y1-y2);
}

int mem(int num) {
  int ret=0;
  if (dist[num] == -1) {
    if (num + d <= maxNum) {
      ret = mem(num+d);
      if (num) ret += getDist(num, num+d);
    }
    dist[num] = ret;
  }
  return dist[num];
}

void solve() {
  int L, R; cin >> L>> R;
  cout << mem(L)-mem(R) << endl; 
}

int main() {
  memset(dist, -1, sizeof(dist));
  cin >> h >> w >> d;
  rep(i, h) rep(j, w) cin >> a[i][j];
  rep(i, h) rep(j, w) mp[a[i][j]] = P(i, j);
  maxNum = h*w;
  rep(i, d) mem(i);
  int q; cin >> q;
  rep(i, q) solve();
  return 0;
}

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

int N;
int A[20];
int x[20][20];
int y[20][20];

int counter(int x) {
  if(x == 0)
    return 0;
  return counter(x >> 1) + (x & 1);
}

/*
int counter(int x) {
  int count = 0;
  while(x) {
    count += x & 1;
    x >>= 1;
  }
  return count;
}
*/

void solve() {
  cin >> N;
  for(int i = 1; i <= N; i++) {
    cin >> A[i];
    for(int j = 1; j <= A[i]; j++) {
      cin >> x[i][j] >> y[i][j];
    }
  }

  int ans = 0;
  for(int bits = 1; bits < (1 << N); bits++) {
    bool ok = true;
    for(int i = 1; i <= N; i++) {
      if(!(bits & (1 << (i-1))))
        continue;
      for(int j = 1; j <= A[i]; j++) {
        if(((bits >> (x[i][j]-1)) & 1) ^ y[i][j])
          ok = false;
      }
    }
    if(ok)
      ans = max(ans, counter(bits));
  }

  cout << ans << endl;
}

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


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include<list>
#include <map>
#define rep(i, n) for(int i = 0; i < n; i++)
#define REP(i, m, n) for(int i = m; i < n; i++)
#define ALL(v) v.begin(),v.end()
#define RALL(v) v.rbegin(),v.rend()
#define check(v) rep(i,v.size()) cout << v[i] << " ";\
cout << endl
#define INF 1e9
typedef long long ll;
using namespace std;

int main() {
    int a,b,c ; cin >> a >> b >> c;
    cout << a+b+c << endl;

    return 0;
}


Measured memory_bytes: 3096
// Math = ♥️

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

#define ll long long
#define ld long double
typedef pair<ll, ll> ii;
typedef vector<ll> vi;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
#define pq priority_queue
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(), (c).end()
#define sz(c) ((ll)c.size())
#define ordered_set                            \
    tree<ll, null_type, less<ll>, rb_tree_tag, \
         tree_order_statistics_node_update>
const ll INF = (ll)(1e12);

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll n, k;
    cin >> n >> k;

    vi h(n);
    for (auto &it : h) {
        cin >> it;
    }

    ll dp[n];

    for (int i = 0; i < n; i++) {
        dp[i] = INF;
    }
    dp[n - 1] = 0;

    for (int i = n - 2; i >= 0; i--) {
        for (int j = 1; j <= k && (i + j) < n; j++) {
            dp[i] = min(dp[i + j] + llabs(h[i] - h[i + j]), dp[i]);
        }
    }

    cout << dp[0] << "\n";
}


Measured memory_bytes: 1792
#include <iostream>
#include <string>
using namespace std;
int b[101];
int main(void){
    int a[3];
    cin>>a[0]>>a[1]>>a[2];
    for(int i=0;i<3;i++){
        b[a[i]]++;
    }
    int ans=0;
    for(int i=0;i<=100;i++){
        if(b[i]!=0)ans++;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N,p=0,w=0,g=0,y=0,a;
  string op;
  cin >> N;
 
  // ここにプログラムを追記
  for(int i = 0; i < N;i++){
    cin >> op;
    
    if (op == "P") {
      p=1;
    }
    else if (op == "W") {
      w=1;
    }
    else if (op == "G") {
      g=1;
    }
    else if (op == "Y") {
      y=1;
    }
  }
  a = p+w+g+y;
  if(a == 3){
    cout << "Three";
  }
  else if(a == 4){
  cout << "Four";
  }
  else
    cout << "error";
}

Measured memory_bytes: 256
#include <stdio.h>
using namespace std;
int N;
int i = 2;
int num;
int main()
{

  scanf("%d", &N);
  long long ans = (long long)N * (N + 1) - 1;

  for (; i * i <= N; i++)
  {
    num = N / i;
    ans += (long long)i * ((long long)num * num - i * i + num);
  }
  printf("%lld", ans);
}


Measured memory_bytes: 1732
#include<iostream>
#include<cmath>
#include<algorithm>
#include<string>
using namespace std;
int main(){
  int n;cin>>n;
  int i,j;
  int a[n];
  for(i=0;i<n;i++){
    cin>>a[i];
  }
  sort(a,a+n);

  int b[n];
  for(i=0;i<n-1;i++){
    b[i]=a[i+1]-a[i];
  }
  sort(b,b+n);
  int ans=1;
  if(n==2) ans=a[1];
  else{
    int tmp=a[1];
    bool gcd=false;
    for(i=tmp;i>=1;i--){
      int count=0;
      for(j=0;j<n;j++){
        if(a[j]%i!=0) count++;
        if(count==2) break;
      }
      if(count<2){gcd=true;break;}
    }
    if(gcd) ans=i;
  }
  cout<<ans<<endl;
}


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

const int N = 110;
int n;
int d[N][2];

int main() {
    cin >> n;

    int len = 0;
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        if (x == y) {
            len++;
        }
        if (x != y) len = 0;
        if (len == 3) {
            cout<<"Yes\n";
            return 0;
        }
    }

    cout<<"No\n";


    return 0; 
}

Measured memory_bytes: 3636
import java.util.*;

public class Main{
	static private Scanner sc = new Scanner(System.in);
	
	public static void main(String[] args){
		long n = sc.nextLong();
		
		if(n % 2 == 1){
			System.out.println(0);
			return;
		}
		
		long ans = 0;
		for(long num = 10; num <= n; num *= 5){
			ans += n / num;
		}
		
		System.out.println(ans);
	}
}

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

int main() {
	int X, Y, Z, K;
	cin >> X >> Y >> Z >> K;
	vector<long long> A(X), B(Y), C(Z);
	for (int i = 0; i < X; i++) {
		cin >> A[i];
	}
	for (int i = 0; i < Y; i++) {
		cin >> B[i];
	}
	for (int i = 0; i < Z; i++) {
		cin >> C[i];
	}

	vector<long long> AB;
	for (int i = 0; i < X; i++) {
		for (int j = 0; j < Y; j++) {
			AB.push_back(A[i] + B[j]);
		}
	}
	sort(AB.begin(), AB.end());
	reverse(AB.begin(), AB.end());

	vector<long long> ABC;
	for (int i = 0; i < min(K, (int)AB.size()); i++) {
		for (int j = 0; j < Z; j++) {
			ABC.push_back(AB[i] + C[j]);
		}
	}
	sort(ABC.begin(), ABC.end());
	reverse(ABC.begin(), ABC.end());

	for (int i = 0; i < K; i++) {
		cout << ABC[i] << endl;
	}


	return 0;
}

Measured memory_bytes: 43240
import java.util.*;
import java.lang.Math;
public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int A = sc.nextInt();
        int B = sc.nextInt();
        int X = sc.nextInt();
        if(A > X){
            System.out.println("NO");
        }else if(X < A + B){
            System.out.println("YES");
        }else{
            System.out.println("NO");
        }
    }
}
    

Measured memory_bytes: 35552
#include<cstdio>
#include<cmath>

int a,b,c;

int main()
{
	scanf("%d %d %d",&a,&b,&c);
	int flag = 0;
	for(int k = 1;k <= 10000005;k++){
		if((b * k + c) % a == 0) {
			printf("YES\n");
			flag = 1;
			break;
		}
	}
	if(!flag) printf("NO\n");
	return 0;
}

Measured memory_bytes: 128
import core.bitop;
import std.algorithm;
import std.ascii;
import std.bigint;
import std.conv;
import std.functional;
import std.math;
import std.numeric;
import std.range;
import std.stdio;
import std.string;
import std.random;
import std.typecons;
import std.container;

alias sread = () => readln.chomp();
long bignum = 1_000_000_007;

T lread(T = long)()
{
    return readln.chomp.to!T();
}

T[] aryread(T = long)()
{
    return readln.split.to!(T[])();
}

void scan(TList...)(ref TList Args)
{
    auto line = readln.split();
    foreach (i, T; TList)
    {
        T val = line[i].to!(T);
        Args[i] = val;
    }
}

void main()
{
    long a, b, c, d;
    scan(a, b, c, d);
    long e = gcd(c, d);
    e = min(c, d) * (max(c, d) / e);
    long f = b / c - a / c + !(a % c);
    long g = b / d - a / d + !(a % c);
    long h = b / e - a / e + !(a % c);
    long i = f + g - h;
    (b - a - i + 1).max(0).writeln();
}


Measured memory_bytes: 256
#include <iostream>
#include <utility>
#include <map>
#include <vector>
#include <algorithm>
#include <queue>
#include <math.h>
#include <stack>
#include <set>
#include <deque>
#include <cmath>

using namespace std;
typedef long long ll;
ll mod = 1e9+7;
//ll mod = 998244353;
#define rep(i,n) for(int i = 0; i < (n); ++i)

ll keta (ll a) {
    if (a == 0) return 1;
    ll ret = 0;
    while(1) {
        if (a == 0) break;
        ++ret;
        a /= 10;
    }
    return ret;
}

int main() {
    ll n;
    cin >> n;
    ll ans = 1e18;
    for (ll i = 1; i * i <= n; ++i) {
        if (n % i == 0) {
            //cout << i << " " << (n/i) << " " << keta(i) << " " << keta(n/i) << endl;
            ans = min(ans, max(keta(i), keta((n / i))));
        } 
    }
    cout << ans << endl;
    return 0;
}


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

#define REP(i, n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i, m, n) for(int i = (m); i < (int)(n); ++i)
#define INF 2000000000

#ifdef LOCAL
  #define eprintf(...) fprintf(stdout, __VA_ARGS__)
#else
  #define eprintf(...) 0
#endif

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef unsigned int uint;

int ctoi(char c) {
  return c - '0';
}

template <class C>
void printContainer(C &container, const char *delim=",") {
  for(const auto &e : container) {
    std::cout << e << delim;
  }
  std::cout << "\n";
}

// Greatest common divisor
template<class T>
T gcd(T x, T y) {
  if(x < y) {
    std::swap(x, y);
  }
  T r = x % y;
  while(r != 0) {
    x = y;
    y = r;
    r = x % y;
  }
  return y;
}

// Least common multiple
template<class T>
T lcm(T x, T y) {
  return (x*y)/gcd(x,y);
}

int main() {
  int x, y;
  cin >> x >> y;
  string ans = "No";
  vector<vector<int>> vvi {{1,3,5,7,8,10,12}, {4,6,9,11}, {2}};
  for(auto &v : vvi) {
    bool res1 = find(v.begin(), v.end(), x) != v.end();
    bool res2 = find(v.begin(), v.end(), y) != v.end();
    if(res1 && res2) {
      ans = "Yes";
    }
  }
  

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
constexpr long double EPS = 1e-15;
const long double PI = acos(-1);
constexpr int inf = 1e9;
constexpr ll INF = 2e18;
constexpr ll MOD = 1e9+7;
constexpr ll MOD1 = 998244353;
typedef pair<ll,ll> P;
//#define all(v) (v).begin(), (v).end()
#define rep(i,a,b) for (int i = (a); i < (b); i++)
#define REP(i,n) rep(i,0,n)
#define sz(s) (s).size()
#define pb push_back
#define fi first
#define se second
//#define mp make_pair

ll n,m,p;
ll from[6000],to[6000],cost[6000];
vector<pair<ll,ll>> G[3000];

void input() {
    cin >> n >> m >> p;
    REP(i,m) {
        cin >> from[i] >> to[i] >> cost[i];
        from[i]--;
        to[i]--;
        cost[i] -= p;
        G[from[i]].pb({to[i],cost[i]});
    }
}

bool from0[3000], fromn[3000];

void dfs0(int k) {
    if (from0[k]) return;
    from0[k] = 1;
    for (int i = 0; i < G[k].size(); i++) {
        dfs0(G[k][i].fi);
    }
}

void dfsn(int k) {
    if (fromn[k]) return;
    fromn[k] = 1;
    for (int i = 0; i < G[k].size(); i++) {
        dfsn(G[k][i].fi);
    }
}

ll d[3000];

void solve() {
    from0[0] = 1;
    fromn[n - 1] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (from0[from[j]]) from0[to[j]] = 1;
            if (fromn[to[j]]) fromn[from[j]] = 1;
        }
    }

    REP(i,n) d[i] = -INF;
    d[0] = 0;
    ll ma = -INF;
    for (int i = 0; i <= 2 * n; i++) {
        ll pre[3000];
        for (int j = 0; j < n; j++) {
            pre[j] = d[j];
        }
        for (int j = 0; j < m; j++) {
            d[to[j]] = max(d[to[j]], d[from[j]] + cost[j]);
        }
        bool f = 0;
        for (int j = 0; j < n; j++) {
            if (pre[j] != d[j] && from0[j] && fromn[j]) f = 1;
        }
        if (!f) break;
        if (i == 2 * n) {
            cout << -1 << endl;
            return;
        }
        ma = max(ma, d[n - 1]);
    }
    cout << max(ma,0LL) << endl;
}

int main(int argc, char *argv[]){
    input();
    solve();
    return 0;
}


Measured memory_bytes: 640
S = input()

cnt = 0
ans = 0
n = 0
len_S = len(S)

while n < len_S:
  if S[n]== "A":
    cnt += 1
  elif S[n] == "B":
    if n < len_S-1:
      if S[n+1] == "C":
        ans += cnt
        n += 1
      else:
        cnt = 0
  else:
    cnt = 0
  n += 1
print(ans)

Measured memory_bytes: 9312
#include <stdio.h>
#include <string.h>

int judge(int w, int h, int pw, int ph){// (w, h) < (pw, ph)??????0 ?????????1?????????
	if(w*w+h*h < pw*pw+ph*ph) return 0;
	else if(w*w+h*h > pw*pw+ph*ph) return 1;
	if(h < ph) return 0;
	else return 1;
}

int main()
{
	int w, h, mw = 152, mh = 151;
	int iw, ih;
	while(1){
		scanf("%d %d", &ih, &iw);
		if(iw == 0 && ih == 0) break;
		for (h = 1; h <= 150; h++)
		{
			for (w = h+1; w <= 150; w++)
			{
				if(w == iw && h == ih) continue;
				if(judge(w, h, iw, ih)){
					if(judge(mw, mh, w, h)){
						mw = w;
						mh = h;
					}
				}
			}
		}
		printf("%d %d\n", mh, mw);
		mw = 152;
		mh = 151;
	}
	return 0;
}

Measured memory_bytes: 1028
using System;

namespace Ssearch
{
    class Program
    {
        static void Main(string[] args)
        {
            string s1 = Console.ReadLine();
            string p = Console.ReadLine();
            string s2 = s1;
            string s = s1 + s2;
            int ans = s.IndexOf(p);
            if (ans != -1)
            {
                Console.WriteLine("Yes");
            }
            else
            {
                Console.WriteLine("No");
            }
        }
    }
}

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

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

  int ans = 0;
  int list[50][2] = {0};
  for (int i = 1; i <= n - 1; i++) {
    for (int j = 0; j < n; j++) {
      int x = s[j] - 'a';
      if (j < i) {
        list[x][0] = 1;
      }
      else {
        list[x][1] = 1;
      }
    }
    int cnt = 0;
    for (int j = 0; j < 50; j++) {
      if (list[j][0] == 1 && list[j][1] == 1) {
        cnt++;
      }
    }
    if (ans < cnt) {
      ans = cnt;
    }
    for (int j = 0; j < 50; j++) {
      list[j][0] = 0;
      list[j][1] = 0;
    }
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
n = int(input())
count = 0

for i in range(1, 1001):
  for j in range(i, 1000001):
    m = n - i * j
    if m > 0:
      if i == j:
        count += 1
      else:
        count += 2
    if m <= 0:
      break
print(count)

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

typedef long long int ll;
typedef unsigned long long int ull;
#define rep(i,n) for(auto i=0;i<(n);i++)
#define rep1(i,n) for(auto i=1;i<=(n);i++)
#define all(x) (x).begin(),(x).end()

using namespace std;


struct init{ init(){ cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20); }; }aaaaaaa;

ll mod = 1e9 + 7;

int main(){
    ll h, w;
    cin >> h >> w;
    set<ll> hmax;
    set<ll> wmax;
    ll v;
    rep(i, h) cin >> v, hmax.insert(v);
    rep(i, w) cin >> v, wmax.insert(v);

    if((ll)hmax.size() != h || (ll)wmax.size() != w){
        cout << 0 << endl;
        return 0;
    }
    
    ll res = 1;
    ll hcnt = h;
    ll wcnt = w;
    for(ll v = 1; v <= h*w; v++){
        if(*wmax.begin() == v-1){
            wcnt--;
            wmax.erase(*wmax.begin());
        }
        if(*hmax.begin() == v-1){
            hcnt--;
            hmax.erase(*hmax.begin());
        }        
        if(hmax.count(v) && wmax.count(v)) continue;

        if(hmax.count(v))       res *= wcnt;
        else if(wmax.count(v))  res *= hcnt;
        else                    res *= hcnt*wcnt - (h*w-v);

        res %= mod;
        if(res == 0){
            cout << res << endl;
            return 0;
        }
    }

    cout << res << endl;
    
    return 0;
}



Measured memory_bytes: 384
#n, m, q = map(int, input().split())
#List = list(map(int, input().split()))
#req = [list(map(int, input().split())) for _ in range(q)]
#t = t[:-1]
#print(ans[j], end = "") 改行無しで出力
#[0]*n
a = input()

if a.islower() == True:
    print("a")
else:
    print("A")


Measured memory_bytes: 9008
#include<bits/stdc++.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<iomanip>
#include<queue>
#include<cmath>
#include<stack>
#include <map>
#define ll long long int
#define skip cin>>ws;
#define vll vector<ll> 
#define vb vector<bool>
#define vpll vector<pair<ll,ll>>
#define vvll vector<vector<ll>>
#define pll pair<ll,ll>
#define vs vector<string>
#define vvpll vector<vector<pair<ll, ll>>>
#define pb push_back
#define pob pop_back()
#define MOD (ll)(1e9 + 7)
#define test ll t; cin>>t; while(t--)

using namespace std;

void enter(vll &ar)
{
    ll n = ar.size();

    for(ll i=0;i<n;i++)
    {
        cin>>ar[i];
    }
}

void show(vll &a)
{
    ll n = a.size();

    for(ll i=0;i<n;i++)
    {
        cout<<a[i]<<" ";
    }
    cout<<"\n";
}

void SieveOfErat1sthenes(int n, vll &pri) 
{ 
    vb prime(n+1, true); 
   
    for (int p=2; p*p<=n; p++) 
    { 
        
        if (prime[p] == true) 
        { 
            pri.pb(p);
            
            for (int i=p*p; i<=n; i += p) 
                prime[i] = false; 
        } 
    } 
}

ll mo(ll a)
{
    return a%MOD;
}

bool compare(pll a, pll b)
{
    return a.first>b.first;
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string s, t;
    cin>>s>>t;

    ll n = s.size(), m = t.size();

    vvll mat(n+1, vll(m+1, 0));

    for(ll i=1;i<=n;i++)
    {
        for(ll j=1;j<=m;j++)
        {
            if(s[i-1]==t[j-1])
            {
                mat[i][j] = 1 + mat[i-1][j-1];
            }
            else
            {
                mat[i][j] = max(mat[i][j-1], mat[i-1][j]);
            }
        }
    }

    ll i = n, j = m;
    vector<char> ans;

    while(i>0&&j>0)
    {
        if(s[i-1]==t[j-1])
        {
            ans.pb(s[i-1]);
            j--;
            i--;
        }
        else
        {
            if(mat[i-1][j]>mat[i][j-1])
            {
                i--;
            }
            else
            {
                j--;
            }
        }
    }

    reverse(ans.begin(), ans.end());

    for(auto ele: ans) cout<<ele;
    cout<<"\n";

    return 0;
}


Measured memory_bytes: 73652
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define FOR(i,start,end) for(int i=start;i<=end;i++)
const int INF = 1001001001;
using namespace std;
typedef long long ll;

int main()
{
  int a,b,c;
  int res=1;
  cin >> a>>b>>c;

  if(a!=b) res++;
  if(a!=c && b!=c) res++;

  cout << res << endl;
}


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

typedef long long LL;
typedef vector<int> vi;
typedef vector<LL> vl;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

#define fast ios_base::sync_with_stdio(0),cin.tie(0)
#define temp template<typename T>
#define debug(x) cerr<<"Line "<<__LINE__<<": "<<#x<<" = "<<x<<'\n'
#define itr(it,x) for(__typeof(x.begin()) it=x.begin();it!=x.end();it++)
#define rep(i,a,b) for(int i=a;i<=(int)b;i++)
#define repr(i,a,b) for(int i=a;i>=(int)b;i--)
#define cas(n) printf("Case %d:",(int)n)
#define mem(x,v) memset(x,v,sizeof(x))
#define read(x) freopen(x,"r",stdin)
#define write(x) freopen(x,"w",stdout)
#define all(x) x.begin(),x.end()
#define aut(x,v) for(auto &x:v)
#define ini(n) scanf("%d",&n)
#define inl(n) scanf("%lld",&n)
#define ind(n) scanf("%lf",&n)
#define ins(n) scanf("%s",n)
#define insn(n) scanf(" %[^\n]",n)
#define outi(n) printf("%d",(int)n)
#define outl(n) printf("%lld",(LL)n)
#define outd(n,p) printf("%.*lf",p,(double)n)
#define outs(n) printf("%s",n)
#define sz(x) (int)x.size()
#define nl printf("\n")
#define sp printf(" ")
#define pb push_back
#define mp make_pair
#define xx first
#define yy second

const int inf=0x3f3f3f3f;
const int mod=1000000007;
const int mx=100005;
const LL  infL=0xf3f3f3f3f3f3f3f;
const double eps=1e-9;
const double pi=acos(-1.0);

int main()
{
    //read("in.txt"),write("out.txt");
    int n,h,w,cnt=0,x,y;
    ini(n),ini(h),ini(w);
    while(n--)
    {
        ini(x),ini(y);
        if(x>=h&&y>=w)
            cnt++;
    }
    outi(cnt),nl;
    return 0;
}


Measured memory_bytes: 256
import scala.io.StdIn.readLine

object Main {

  def sum(n:Int, s:Int, x:Int):Int = {
    if(n==1) {
      if(s >= 0 && s<=9 && s > x ) 1 else 0
    } else { for(i <- 0 to 9 if s>=i && i>x) yield sum(n-1,s-i,if(i>x) i else x) }.sum
  }

  def getSum(sb:StringBuilder):Unit = {
    val r = readLine.split(" ").map(_.toInt)

    if(r(0)==0 && r(1)==0)  print(sb.result)
    else {
      println(sum(r(0),r(1),-1))
      getSum(sb)
    }
  }

  def main(args:Array[String]) = getSum(new StringBuilder)
}

Measured memory_bytes: 46264
N=int(input())
a=list(map(int,input().split()))
four =0
two =0
odd = 0
       
for num in a:
  if num%4==0:
    four +=1
  if num%2==0:
    two += 1
       
two -= four
odd=N-four-two       
#print(four,two,odd)

if four >=1:
  if odd==four+1:
    if two==0:
      print("Yes")
    else:
      print("No")
  elif odd<four+1:
    print("Yes")  
  else:
    print("No")
else:
  if odd>=1:
    print("No")
  else:
    print("Yes")

#if four>=N//2:
#  print("Yes")
#else:
#  if two >=imp:
#    print("Yes")
#  else:
#    print("No")

Measured memory_bytes: 14228
S = input()
C_count = 0
C_pos = 0
upper_flag = True
AC_flag = False
if S[0] == 'A':
    for i, c in enumerate(S[2:-1]):
        if c == 'C':
            C_count += 1
            C_pos = i+2
    if C_count == 1:
        for i, c in enumerate(S[1:]):
            if (i+1 != C_pos):
                if c.isupper():
                    upper_flag = False
        if upper_flag:
            print('AC')
            AC_flag = True

if not AC_flag:            
    print('WA')


Measured memory_bytes: 3060
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define N 123
inline int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<3)+(x<<1)+c-'0';
        c=getchar();
    }
    return x*f;
}
int n,dp[N][N],m;
char s[N][N];
int main(){
	n=read(),m=read();
	for(int i=1;i<=n;++i){
		scanf("%s",s[i]+1);
	}
	memset(dp,0x3f,sizeof(dp));
	dp[1][1]=(s[1][1]=='#'?1:0);
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			if(i==1&&j==1)continue;
			dp[i][j]=min(dp[i-1][j]+(s[i][j]=='#'&&s[i-1][j]=='.'),dp[i][j-1]+(s[i][j]=='#'&&s[i][j-1]=='.'));
		}
	}
	printf("%d\n",dp[n][m]);
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
typedef long long ll;
const int N=1e5+5;
ll n;
int m;
ll a[N],s[N];
int pos[N];
int main(){
    // freopen("a.in","r",stdin);
    // int T;scanf("%d",&T);for(int tttt=1;tttt<=T;tttt++){
    if(1){
    scanf("%lld%lld%d",&n,&a[1],&m);
    s[1]=a[1];
    int cirpos,cirlen;
    for(int i=2;;i++){
        a[i]=a[i-1]*a[i-1]%m;
        s[i]=s[i-1]+a[i];
        if(pos[a[i]]){
            cirpos=pos[a[i]];
            cirlen=i-cirpos;
            break;
        }
        pos[a[i]]=i;
    }
    if(n<cirpos+cirlen){
        printf("%lld\n",s[n]);
    }
    else{
        long long ans=s[cirpos-1];
        n-=cirpos-1;
        ans+=(s[cirpos+cirlen-1]-s[cirpos-1])*(n/cirlen);
        ans+=s[cirpos+n%cirlen-1]-s[cirpos-1];
        printf("%lld\n",ans);
    }
    }return 0;
}


Measured memory_bytes: 4920
#include<bits/stdc++.h>
#include <queue>
#include <cstring>
#define mp make_pair
#define pb push_back
#define p push

#define FOR(a,c) for(int a = 0;a<c;a++)
#define ll long long int

#define getI(a) scanf("%d",&a)
#define getII(a,b) scanf("%d%d",&a,&b)
#define getIII(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define getL(a) scanf("%lld",&a)
#define getLL(a,b) scanf("%lld%lld",&a,&b)
#define BEND(c) (c).begin(),(c).end()
#define BEND2(c) (c).rbegin(),(c).rend()
#define fi first
#define se second
#define pi 3.1415926535897932384626
#define getS(a) scanf("%s",a)
#define pfi(a) printf("%d",a);
#define pfii(a,b) printf("%d%d",a,b);
#define pfl(a) printf("%lld",a);
#define pfll(a,b) printf("%lld%lld",a,b);
#define pfd(a) printf("%lf",a);
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);

#define sag (sol|1)
#define sol (root<<1)
#define ort (bas+son)/2
#define SIZE 1000000007
#define MAXN 100005
using namespace std;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<long long> vl;
typedef vector<pair<int, int>> vpi;
typedef vector<pair<long long, long long>> vpl;
typedef pair<int, int> pii;
typedef pair <ll, ll> pll;
typedef vector<vi> graph ;


int main (){
   double x;
   cin >>x;
   x/=1.08;

    int k = x;
   x*=1.08;
  if(k * 1.08 < x)k++;
  if(k *1.08 < x+1 )cout<<k;
  else cout<<":(";




    return 0;
}

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

class Problem {
    public static void Main() {
        var str = "";
        while ((str = Console.ReadLine()) != "-1 -1 -1") {
            var data = str.Split().Select(int.Parse).ToArray();
            Console.WriteLine(data[0] == -1 || data[1] == -1 ? "F" :
                              data[0] + data[1] >= 80        ? "A" :
                              data[0] + data[1] >= 65        ? "B" :
                              data[0] + data[1] >= 50        ? "C" :
                              data[0] + data[1] >= 30        ? (data[2] >= 50 ? "C" : "D") : "F");
        }
    }
}


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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define reps(i, n, m) for (int i = (int)(n); i <= (int)(m); i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define ceiv(a, b) (1 + (int)((a) - 1)/(int)(b))
//#define int long long

signed main(){
    int n, d, x;
    cin >> n >> d >> x;
    rep(i,n){
        int a; cin >> a;
        x += 1 + (d-1)/a;
    }
    cout << x << endl;
}

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


int main()
{
    int l, r, d;
    cin >> l >> r >> d;
    int ans = 0;
    for(int i = l; i <= r; i++)
    {
        if(i % d == 0) ans++;
    }
    cout << ans << endl;
    
    return 0;
}

Measured memory_bytes: 3620
using System;

public class Hello
{
    public static void Main()
    {
        string[] line = Console.ReadLine().Trim().Split(' ');
        var a = Array.ConvertAll(line, int.Parse);
        Array.Sort(a);
        Console.WriteLine(a[0] == 5 && a[1] == 5 && a[2] == 7 ? "YES":"NO");
    }
}


Measured memory_bytes: 11220
/*
author:w2sc
date:2019/12/19
time:20:10:42
*/
#include <bits/stdc++.h>
#define ull unsigned long long
#define ll long long
using namespace std;
const double EPS=1e-10;
int dcmp(double x){return x<-EPS?-1:x>EPS;}
struct Point{
    double x,y;
    Point(){}
    Point(double xx,double yy){x=xx,y=yy;}
    Point operator -(Point A){return Point(x-A.x,y-A.y);}
    double operator ^(Point A){return x*A.y-y*A.x;}
    double operator *(Point A){return x*A.x+y*A.y;}
};
typedef Point Vec;
struct Line{
    Point A,B;
    Vec v;
    Line(){}
    Line(Point AA,Point BB){A=AA,B=BB;v=B-A;}
    bool on_seg(Point P){return dcmp((A-P)^(B-P))==0 && dcmp((A-P)*(B-P))<=0;}
};
int q;
int main()
{
    scanf("%d",&q);
    while(q--)
    {
        Point A,B;
        Line a,b;
        scanf("%lf%lf%lf%lf",&A.x,&A.y,&B.x,&B.y);
        a=Line(A,B);
        scanf("%lf%lf%lf%lf",&A.x,&A.y,&B.x,&B.y);
        b=Line(A,B);
        printf("%d\n",(dcmp(((b.A-a.A)^(a.v))*((b.B-a.A)^a.v))<0 &&
            dcmp(((a.A-b.A)^(b.v))*((a.B-b.A)^b.v))<0) ||
            b.on_seg(a.A) || b.on_seg(a.B) || a.on_seg(b.A) || a.on_seg(b.B));
    }
    return 0;
}



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

public class Main 
{

	public static void main(String[] args) 
	{
		Scanner scan = new Scanner(System.in);
		
		while(true)
		{
			int ruleNum = scan.nextInt();
			int packNum = scan.nextInt();
			ArrayList<Rule> rules = new ArrayList<Rule>();
			ArrayList<String> okpacks = new ArrayList<String>();
			
			if(ruleNum == 0 && packNum == 0)
			{
				break;
			}
			
			for(int i = 0; i < ruleNum; i++)
			{
				String type = scan.next();
				if(type.equals("permit"))
				{
					rules.add(new Rule(scan.next(), scan.next(), 1));
				}
				
				if(type.equals("deny"))
				{
					rules.add(new Rule(scan.next(), scan.next(), 0));
				}
			}
			
			for(int i = 0; i < packNum; i++)
			{
				String ip1 = scan.next();
				String ip2 = scan.next();
				String content = scan.next();
				
				int status = 0;
				
				for(int r = 0; r < rules.size(); r++)
				{
					Rule rul = rules.get(r);
					
					if(rul.ip1matches(ip1) && rul.ip2matches(ip2))
					{
						//affected
						status = rul.type;
					}
				}
				
				if(status == 1)
				{
					okpacks.add(ip1 + " " + ip2 + " " + content);
				}
			}
			
			//print all okpacks
			System.out.println(okpacks.size());
			for(String pack : okpacks)
			{
				System.out.println(pack);
			}
		}
	}
	
	static class Rule
	{
		String ip1 = "";
		String ip2 = "";
		int type;
		
		public Rule(String ip1, String ip2, int type)
		{
			this.ip1 = ip1;
			this.ip2 = ip2;
			this.type = type;
		}
		
		boolean ip1matches(String enter)
		{
			for(int i = 0; i < ip1.length(); i++)
			{
				String curlet1 = ip1.substring(i, i+1);
				String curlet2 = enter.substring(i, i+1);
				
				if(!curlet1.equals(curlet2) && !curlet1.equals("?"))
				{
					return false;
				}
			}
			
			return true;
		}
		
		boolean ip2matches(String enter)
		{
			for(int i = 0; i < ip2.length(); i++)
			{
				String curlet1 = ip2.substring(i, i+1);
				String curlet2 = enter.substring(i, i+1);
				
				if(!curlet1.equals(curlet2) && !curlet1.equals("?"))
				{
					return false;
				}
			}
			
			return true;
		}
	}
}



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

using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
#define ll long long int
#define INF 1000000007
// cin.eof() 入力個数の問題
int main() {
    string s;
    cin >> s;
    int q;
    cin >> q;
    bool flag = false;
    rep(i, q) {
        int a;
        cin >> a;
        if (a == 1) {
            flag =! flag;
        } else {
            int c;
            string f;
            cin >> c >> f;
            if ((!flag && c == 1) || (flag && c == 2)) {
                s.insert(0,f);
            } else {
                s.push_back(f[0]);
            }
        }
   // cout<<flag<<s<<endl;
    }
    if(flag){
      reverse(s.begin(),s.end());
    }
    cout<<s<<endl;
    return 0;
}


Measured memory_bytes: 900
#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;
typedef long long ll;
int n,k;
vector<ll> a;
ll dp[110][100010];
ll mod = 1000000007;

int main(){
 cin >> n >> k;
 a.resize(n);
 for(int i = 0; i < n; ++i) cin >> a[i];
 for(int i = 0; i <= n; ++i) dp[i][0] = 1; 

 for(int i = 1; i <= n; ++i){
   for(int j = 1; j <= k; ++j){
     dp[i][j] = (dp[i - 1][j] + dp[i][j - 1])%mod;
     if(j - a[i - 1] - 1 >= 0){
       dp[i][j] = (dp[i][j] + mod - dp[i - 1][j - a[i - 1] - 1])%mod;
     }
   }
 }
 cout << dp[n][k] << endl;
 return 0;
}

Measured memory_bytes: 79360
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define N 100010
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return x*f;
}
int n,a[N],h[N],num=0,du[N],fa[N];
struct edge{
	int to,next;
}data[N<<1];
bool dfs(int x){
	if(du[x]==1) return 1;
	ll sum=0;int mx=0;
	for(int i=h[x];i;i=data[i].next){
		int y=data[i].to;if(fa[x]==y) continue;
		fa[y]=x;if(!dfs(y)) return 0;mx=max(mx,a[y]);sum+=a[y];
	}if(a[x]>sum) return 0;if(a[x]==sum) return 1;
	ll res= mx>sum-mx?sum-mx:sum/2;//内部交流最多res对
	if(sum-a[x]>res||a[x]-(sum-a[x])<0) return 0;
	a[x]-=sum-a[x];return 1; 
}
int main(){
//	freopen("a.in","r",stdin);
	n=read();for(int i=1;i<=n;++i) a[i]=read();
	for(int i=1;i<n;++i){
		int x=read(),y=read();du[x]++;du[y]++;
		data[++num].to=y;data[num].next=h[x];h[x]=num;
		data[++num].to=x;data[num].next=h[y];h[y]=num;
	}if(n==2){puts(a[1]==a[2]?"YES":"NO");return 0;}
	for(int i=1;i<=n;++i)
		if(du[i]!=1){
			if(!dfs(i)) puts("NO");
			else puts(a[i]?"NO":"YES");return 0;
		}
}


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

int N;
int a[100];

int solve(){
	int max=0;
	int min=0;
	int color[9] = {};
	for(int i=0; i<N; i++){
		if(1<=a[i]&&a[i]<=399) color[0]+=1;
		else if(400<=a[i]&&a[i]<=799) color[1]+=1;
		else if(800<=a[i]&&a[i]<=1199) color[2]+=1;
		else if(1200<=a[i]&&a[i]<=1599) color[3]+=1;
		else if(1600<=a[i]&&a[i]<=1999) color[4]+=1;
		else if(2000<=a[i]&&a[i]<=2399) color[5]+=1;
		else if(2400<=a[i]&&a[i]<=2799) color[6]+=1;
		else if(2800<=a[i]&&a[i]<=3199) color[7]+=1;
		else color[8]+=1;	
	}
	for(int i=0;i<8;i++){
		if(color[i] != 0){
			max+=1;
			min+=1;
		}
	}
	max+=color[8];

	if(min==0) min=1;

	cout << min << " " << max << endl;
	return 0;
}


int main(){
	cin >> N;
	for(int i=0; i<N; i++){
		cin >> a[i];
	}
	solve();
	return 0;
}

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

int main() {
  int N, A, b;
  cin >> N;
  A = 0;
  b = N;
  while (N != 0) { 
    A = A + N % 10;
    N = N / 10;
  }
  if (b % A == 0) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}


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

#define INF 1.1e9
#define LINF 1.1e18
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define BIT(x,n) bitset<n>(x)
#define PI 3.14159265358979323846

typedef long long ll;
typedef pair<string,int> P;
typedef pair<int,P> PP;

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

int h,w,d;
string s[100];
int cnt,ans;

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

	cin>>h>>w>>d;
	REP(i,h) cin>>s[i];
	REP(i,h) {
		cnt=0;
		REP(j,w) {
			if(s[i][j]=='#') cnt=0;
			else cnt++,ans+=(int)(cnt>=d);
		}
	}
	REP(j,w) {
		cnt=0;
		REP(i,h) {
			if(s[i][j]=='#') cnt=0;
			else cnt++,ans+=(int)(cnt>=d);
		}
	}
	cout<<ans<<endl;

	return 0;
}



Measured memory_bytes: 3152
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <queue>
#include <set>
#include <map>

using namespace std;
typedef long long ll;

template <typename T>
struct segtree{
    int n;
    T UNIT;
    vector<T> dat;
    segtree(int n_, T unit){
        UNIT = unit;
        n = 1;
        while(n < n_) n *= 2;
        dat = vector<T>(2*n);
        for(int i = 0; i < 2*n; i++) dat[i] = UNIT;
    }

    T calc(T a, T b){
        T ans;
        ans = min(a, b);
        return ans;
    }
    void insert(int k, T a){
        dat[k+n-1] = a;
    }
    void update_all(){
        for(int i = n-2; i >= 0; i--){
            dat[i] = calc(dat[i*2+1], dat[i*2+2]);
        }
    }
    //k番目の値(0-indexed)をaに変更
    void update(int k, T a){
        k += n-1;
        dat[k] = a;
        while(k > 0){
            k = (k-1)/2;
            dat[k] = calc(dat[k*2+1], dat[k*2+2]);
        }
    }

    //[a, b)
    //区間[a, b]へのクエリに対してはquery(a, b+1)と呼ぶ
    T query(int a, int b, int k=0, int l=0, int r=-1){
        if(r < 0) r = n;
        if(r <= a || b <= l) return UNIT;
        if(a <= l && r <= b) return dat[k];
        else{
            T vl = query(a, b, k*2+1, l, (l+r)/2);
            T vr = query(a, b, k*2+2, (l+r)/2, r);
            return calc(vl, vr);
        }
    }
};

ll N, E, T;
ll x[100001];
ll x_[100001];
ll dp[100001];
const ll INF = 1e+18;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << setprecision(10) << fixed;
    cin >> N >> E >> T;
    for(int i = 0; i < N; i++){
        cin >> x[i];
        x_[i] = x[i]*2;
    }
    dp[0] = 0;
    segtree<ll> sgt1(N+1, INF), sgt2(N+1, INF);
    sgt1.update(0, dp[0]);
    sgt2.update(0, dp[0]-2*x[0]);
    // cout << dp[0]-x[0] << ' ' << dp[0]-x[0]-2*x[1] << endl;
    for(int i = 0; i < N; i++){
        int ut = upper_bound(x, x+N, x[i] - (T+1)/2)-x-1;
        int lt = lower_bound(x, x+N, x[i] - (T-1)/2)-x;
        // 0~j-1はT/2より大きい幅
        ll tmp1 = INF, tmp2 = INF;
        tmp1 = sgt2.query(0, min(ut+1, i+1))+x[i]*3;
        
        tmp2 = sgt1.query(lt, i+1)+x[i]+T;
        dp[i+1] = min(tmp1, tmp2);
        if(i+1 != N){
            sgt1.update(i+1, dp[i+1]-x[i]);
            sgt2.update(i+1, dp[i+1]-x[i]-2*x[i+1]);
        }
        // cout << ut << ' ' << lt << endl;
        // cout << tmp1 << ' ' << tmp2 << endl;
        // cout << dp[i+1]-x[i] << ' ' << dp[i+1]-x[i]-2*x[i+1] << endl;
        // cout << dp[i+1] << ' ' << endl;
    }
    cout << dp[N]+E-x[N-1] << endl;
}

Measured memory_bytes: 8064
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define repr(i,x,n) for(int i=x; i<(n); i++)
#define ALL(x) (x).begin(),(x).end()
#define INF 1e9
typedef long long ll;
using VI = vector<int>;
using VS = vector<string>;
using graph = vector<vector<int>>;
int main()
{
string c;
cin>>c;
if (c=="a"||c=="i"||c=="u"||c=="e"||c=="o")
{
    cout<<"vowel"<<endl;

}
else
{
    cout<<"consonant"<<endl;
}

    return 0;
}

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

int main()
{
    int n;
    cin >> n;
    vector<long long int> l(n + 1);
    l.at(0) = 2;
    l.at(1) = 1;
    for (int i = 2; i <= n; i++)
    {
        l.at(i) = l.at(i - 1) + l.at(i - 2);
    }
    cout << l.at(n) << endl;
}

Measured memory_bytes: 256