akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#define neparan & 1
using namespace std;

const int mod = 998244353;

int add(int a, int b) {
	a += b;
	if(a >= mod) a -= mod;
	if(a < 0) a += mod;
	return a;
}

int mul(int a, int b) {
	return ((long long)a * b) % mod;
}

int po(int a, int b) {
	if(b == 0) return 1;
	if(b == 1) return a;
	if(b neparan) return mul(po(a, b - 1), a);
	int x = po(a, b / 2);
	return mul(x, x);
}

int dj(int a, int b) {
	return mul(a, po(b, mod - 2));
}

int fa[500000];

int ovrh(int n, int k) {
	return dj(fa[n], mul(fa[k], fa[n - k]));
}

int main() {
	
	fa[0] = 1;
	for(int i = 1; i < 500000; i++) {
		fa[i] = mul(fa[i - 1], i);
	}
	
	long long n, a, b, k;
	cin >> n >> a >> b >> k;
	
	int re = 0;
	
	for(int ca = 0; ca <= n; ca++) {
		long long umn = a * ca;
		if(umn <= k) {
			long long mcb = k-umn;
			if(mcb % b == 0) {//add(mul(ca, a), mul(cb, b)) == k) {
				long long cb = mcb / b;
				if (cb > n) continue;
				re = add(re, mul(ovrh(n, ca), ovrh(n, cb)));
			}
			//cout << k << ' ' << umn << '\n';
		}
	}
	
	cout << re;
	
	return 0;
}

Measured memory_bytes: 2688
#include <stdio.h>
#include<math.h>
int isprime(int);
int main(void){
    int A[10000],s=0,n,i,c;
    scanf("%d",&c);
    for(i=0;i<c;i++){
        scanf("%d",&A[i]);
        n=isprime(A[i]);
        if(n==1){
            s++;
        }
    }
    printf("%d\n",s);
return 0;
}

int isprime(x){
    int i;
  if (x==2){
    return 1;
  }
  if (x<2 || x%2==0) {
    return 0;
  }
  i = 3;
  while (i <= sqrt(x)){
    if (x%i==0){
      return 0;
    }
    i = i + 2;
  }
 return 1;
}


Measured memory_bytes: 2056
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        if (K == 1){
            System.out.println(0);
        }else {
            System.out.println(N-K);
        }
        }
}

Measured memory_bytes: 21972
#include <stdio.h>
#include <string.h>
int main(void){
    int n,a[1000];
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        if (a[i] % 2 == 0){
            if (a[i] % 3 != 0 && a[i] % 5 != 0){
                printf("DENIED");
                return 0;
            }
        }
    }
    printf("APPROVED");
    return 0;
}

Measured memory_bytes: 128
import java.util.Scanner;
class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int day = 25 - sc.nextInt();
    String output = "Christmas";
    for(int i = 0; i < day; i++){
      output += " Eve";
    }
    System.out.println(output);
  }
}

Measured memory_bytes: 21204
/*
AuThOr GaRyMr
技巧:
1.区别对待大数据&小数据！
2.Dp难推时算贡献！
3.long long (尤其乘法)！
4.long long INF 要大
5.Dp on trees: 换根法，每次清空当前的节点和换到的子节点
*/
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define niv vector<int>
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define KEEP while(1)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
using namespace std;
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
typedef pair<mp,mp> superpair;
int main(){
	int len;
	string s;
	cin>>len>>s;
	int res=0;
	rep(i,len){
		if(i&&s[i]==s[i-1]) continue;
		res++;
	}
	cout<<res<<endl;
	return 0;
}


Measured memory_bytes: 512
#include <algorithm>
#include <cmath>
#include <iostream>
#include <limits>
#include <numeric>
#include <type_traits>
#include <unordered_map>
#include <vector>

#define rep(i, x, n) for(int i = x; i < n; i++)
using namespace std;
const long long INF = 1LL << 60;

long long GCD(long long a, long long b) {
    if(b == 0)
        return a;
    else
        return GCD(b, a % b);
}
long long LCM(long long a, long long b) {
    long long g = GCD(a, b);
    return a / g * b;
}
bool compare_by_a(pair<int, long long> a, pair<int, long long> b) {
    if(a.first != b.first) {
        return a.first > b.first;
    } else {
        return a.second < b.second;
    }
}
long long N;
void func(long long cur, int use, long long &counter) {
    if(cur > N) {
        return;
    }
    if(use == 0b111) {
        counter++;
    }
    func(cur * 10 + 7, use | 0b001, counter);
    func(cur * 10 + 5, use | 0b010, counter);
    func(cur * 10 + 3, use | 0b100, counter);
}
int main() {
    cin >> N;
    long long res = 0;
    func(0, 0, res);
    cout << res << endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
    int a,b,c,n,i;
    n=0;
    scanf("%d %d %d",&a,&b,&c);
    for (i = a; i <= b; i++)
    {
        if (c % i == 0)
        {
            n++;
        }
    }
    printf("%d\n",n);
    return 0;
}

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

using ll = long long;
using P = pair<int, int>;
//using P = pair<double, double>;
using edge = struct {int to; ll cost;};

#define rep(i, n) for (int i = 0; i < n; i++)
#define ALL(a) (a).begin(), (a).end()

const int di[] = {-1, 0, 1, 0, 1, 1, -1, -1};
const int dj[] = {0, -1, 0, 1, 1, -1, 1, -1};
const int INF = 1001001001;

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

  // for prime mod
  mint inv() const
  {
    return pow(mod - 2);
  }
  mint &operator/=(const mint a)
  {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const
  {
    mint res(*this);
    return res /= a;
  }
};
struct combination
{
  vector<mint> fact, ifact;
  combination(int n) : fact(n + 1), ifact(n + 1)
  {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i)
      fact[i] = fact[i - 1] * i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i)
      ifact[i - 1] = ifact[i] * i;
  }
  mint operator()(int n, int k)
  {
    if (k < 0 || k > n)
      return 0;
    return fact[n] * ifact[k] * ifact[n - k];
  }
};

void solve()
{
  string s;
  cin >> s;
  int ans = 700;
  rep(i, 3) if(s[i] == 'o') ans += 100;
  cout << ans << "\n";
}

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


Measured memory_bytes: 256
const base = trunc(1e9) + 7;
var a:array[0..2000,0..2000] of int64;
    n,k,i,j:integer;
begin
	readln(n,k);
	a[0,0]:=1;
	for i:=1 to 2000 do
	  begin
        a[i,0]:=1;
	    for j:=1 to 2000 do 
	       a[i,j]:=(a[i-1,j] + a[i-1,j-1]) mod base;
	  end;
    for i:=1 to k do
      writeln((a[k - 1, i - 1] * a[n - k + 1,i]) mod base);
end.

Measured memory_bytes: 31360
s = input()
n = len(s)

res = 0
cnt = [0] * 2019
for i in range(n):
    res = (res + int(s[n-1-i]) * pow(10, i, 2019)) % 2019
    cnt[res] += 1

ans = 0
for c in cnt:
    ans += c * (c-1) // 2
ans += cnt[0]

print(ans)

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

using namespace std;

#define int long long
#define pb push_back

signed main () {
  vector<int> a;
  int tmp;
  for(int i=0;i<3;i++) {
    cin >> tmp;
    a.pb(tmp);
  }
  sort(a.begin(), a.end());
  cout << (a[2] - a[1]) + (a[1] - a[0]) << endl;
}


Measured memory_bytes: 256
using System;

/// <summary>
/// Summary description for Class1
/// </summary>
public class A
{
    public static void Main(string[] args)
	{
        //スペース区切りの整数の入力
        string[] input = Console.ReadLine().Split(' ');

        //splitしたデータを2つの変数(N, K)に代入する
        int N = int.Parse(input[0]);
        int K = int.Parse(input[1]);

        //もしKが1なら、return 0;
        if (K == 1)
        {
            Console.WriteLine(0);
        }
        else
        {
            int ans = N - K;
            Console.WriteLine(ans);
        }
    }

}


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

int main(){
 string a,c,d,e;
  cin>>a>>c;
     if(a[0]==c[2]&&a[1]==c[1]&&a[2]==c[0]){
    cout<<"YES"<<endl;
     }
  else{
    cout<<"NO"<<endl;
    }
     
}


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

int main(){
    ios::sync_with_stdio(false);
    int d,n;
    cin >> d >> n;
    int ans=n;
    if(n==100)ans++;
    for(int i=0;i<d;i++){
        ans*=100;
    }

    cout <<ans<< endl;
}


Measured memory_bytes: 256
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
      int A = sc.nextInt();
      int B = sc.nextInt();
      if((1<=A&&A<=9)&&(1<=B&&B<=9)){
        System.out.println(A*B);
      }else{
        System.out.println(-1);
      }
    }
}
      

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

using ll = long long;
using ld = long double;
using vi = vector<int>;
using vll = vector<ll>;
using P = pair<int, int>;

const int INF = 1e9;
const ll INFLL = 1e18;
const int MOD = 1e9 + 7;
const int NIL = -1;

#define rep(i,n) for(int i=0; i<(n); ++i)
#define all(n) n.begin(),n.end()

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

#define DEBUG

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);
	string s;
	vector<int>nums(26);
	while (getline(cin, s)) {

		for (auto c : s) {
			if (c <= 'z'&&c >= 'a')nums[c - 'a']++;
			if (c <= 'Z'&&c >= 'A')nums[c - 'A'] ++;
		}
	}
	for (int i = 0; i < 26; ++i) {
		cout << char('a' + i) << " : " << nums[i] << endl;
	}
	return 0;
}


Measured memory_bytes: 3164
#include <iostream>
#include <algorithm>
#include <string>
#include <math.h>
#include <utility>
using namespace std;

int main(){
	int n[3] = {};
	int t = 0;
	char s, ans;
	string a[3];
	cin >> a[0] >> a[1] >> a[2];
	while (1){
		if (n[t] == a[t].length()) break;
		s = a[t][n[t]];
		n[t] += 1;
		if (s == 'a') t = 0;
		if (s == 'b') t = 1;
		if (s == 'c') t = 2;
	}
	if (t == 0) ans = 'A';
	if (t == 1) ans = 'B';
	if (t == 2) ans = 'C';
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(void)
{
  int N,A,B,C,D,money_x,money_y,answer,ot;
  scanf("%d%d%d%d%d",&N,&A,&B,&C,&D);
  answer=N/A;
  ot=N%A;
  if(ot>0) answer++;
  money_x=answer*B;

  answer=N/C;
  ot=N%C;
  if(ot>0) answer++;
  money_y=answer*D;
  if(money_x<money_y) printf("%d\n",money_x);
  else  printf("%d\n",money_y);
  return 0;
}



Measured memory_bytes: 2100
N = int(input())
h = list(map(int, input().split()))

INF = 10 ** 12
dp = [INF] * 100010

dp[0] = 0

for i in range(1, N):
    dp[i] = min(dp[i], dp[i-1] + abs(h[i] - h[i-1]))
    if i >= 2:
        dp[i] = min(dp[i], dp[i-2] + abs(h[i] - h[i-2]))

print(dp[N-1])


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



int ddp(vector<int>&nums) {
	if(nums.size()==0 || nums.size()==1) return 0 ;
	int dp[nums.size()] ;
	dp[0] =0 ;
	dp[1] = abs(nums[1]-nums[0]) ;
	for(int i =2;i<nums.size();i++){
		dp[i] = min(dp[i-1]+abs(nums[i]-nums[i-1]) , dp[i-2]+abs(nums[i]-nums[i-2])) ;
	}
	return dp[nums.size()-1] ;
} 

int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int N; cin >> N ;
	vector<int>arr(N) ;
	for(int i =0 ;i<N;i++) {
		cin >> arr[i] ;
	}
    int ans = ddp(arr) ;
	cout << ans ;
}

Measured memory_bytes: 1024
#include<iostream>

using namespace std;

int main(){
  int n, k;
  cin >> n >> k;
  int x[100001];
  for(int i = 0 ; i < n; i++){
    cin >> x[i];
  }
  int mini = 1e9;
  for(int i = 0 ; i < n - k + 1 ; i++){
    if(x[i + k - 1] <= 0){
      if(mini > 0 - x[i]){
        mini = 0 - x[i];
      }
    }
    else if(x[i] >= 0){
      if(mini > x[i + k - 1]){
        mini = x[i + k - 1];
      }
    }
    else{
      if(mini > x[i + k - 1] - x[i] + min(abs(x[i]), x[i + k - 1])) mini = x[i + k - 1] - x[i] + min(abs(x[i]), x[i + k - 1]);
    }
  }

  cout << mini << endl;
}


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

int main(){
  int x,y,s,t[1000],k=0,max[1000];
  
  for(int i=0;i<1001;i++){
    t[i]=0;
  }

  for(;;){
    cin>>x>>y>>s;
    if(x+y+s==0){
      break;
    }
    k+=1;
    int a,b,A,B,C,D;
    for(a=1;s-a-a*x/100>0;a++){
      A=a+a*x/100;
      for(b=1;s-A-b-b*x/100>-1;b++);

      b-=1;
      B=b+b*x/100;
      if(A+B !=s){
	t[a]=0;
	continue;
      }

      C=a+a*y/100;
      D=b+b*y/100;
      t[a]=C+D;
    }
    int M=t[0];
    for(int i=0;i<a;i++){
      if(t[i]>M){
	M=t[i];
      }
    }
    max[k]=M;
  }
  for(int i=1;i<=k;i++){
    cout<<max[i]<<endl;
  }
}

Measured memory_bytes: 1164
#include<bits/stdc++.h>
using namespace std;
int main()
{ string s; int cnt=0;
cin>>s;
int n=s.size() ;
for(int i=0 ; i<n ; i++){
int d= s[i]-'0' ;
if(d==1)
cnt++ ; }
cout<< cnt << "\n";

return 0;

}


Measured memory_bytes: 3592
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <set>
#include <queue>
using namespace std;
typedef long long LL;
const int inf = 1 << 30;
const LL INF = 1LL << 60;
const int MaxN = 105;
const double eps = 1e-6;
const double PI = acos(-1.0);

int n, top;
struct Point {
	LL x, y;
	int pos;
	double pb;
	Point () {}
	Point (LL a, LL b) {
		x = a; y = b;
	}
	bool friend operator < (const Point a, const Point b) {
		if(a.y == b.y) return a.x < b.x;
		else return a.y < b.y;
	}
	bool friend operator == (const Point a, const Point b) {
		return (a.x == b.x) && (a.y == b.y);
	}
	Point friend operator + (const Point a, const Point b) {
		return Point(a.x + b.x, a.y + b.y);
	}
	Point friend operator - (const Point a, const Point b) {
		return Point(a.x - b.x, a.y - b.y);
	}
}PP[MaxN + 5];
Point hull[MaxN + 5];               //存放凸包的数组

typedef Point Vector;               //向量和点一样,都有x、y元素,所以这里就偷了个懒

LL Dis(Point A, Point B) {
	return (A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y);
}

double dis(Point A, Point B) {      //两点的距离
	return sqrt(1.0 * Dis(A, B));
}

LL Cross(Vector A, Vector B) {     //叉积
	return A.x * B.y - A.y * B.x;
}

bool Gcmp(Point A, Point B) {       //按照极角从大到小排序
	Point O = PP[1];                //最下方的点一定在凸包上,将其作为原点进行极角排序
	LL tmp = Cross(A - O, B - O);
	//向量OA和OB的叉积
	//其实也可以直接写成Cross(A - O, B - O),那样写只是为了便于理解

	if(tmp == 0) {                  //叉积为0,共线;所以离原点近的排在前面
		if(Dis(A, O) < Dis(B, O)) return true;
		else return false;
	}
	else {                          //不为0,不共线
		if(tmp > 0) return true;    //大于0,说明向量OB在向量OA的左边,所以OA排在前面
		else return false;          //反之,OB排在前面
	}
}

void Graham() {                     //求凸包
	sort(PP + 1, PP + n + 1);       //排序找出最下方的点,作为原点
	sort(PP + 2, PP + n + 1, Gcmp); //对其余的点进行极角排序
	hull[1] = PP[1];
	hull[2] = PP[2];
	top = 2;
	for(int i = 3; i <= n; i++) {
		while(top >= 2 && Cross(hull[top] - hull[top - 1], PP[i] - hull[top - 1]) < 0)
			top--;
		hull[++top] = PP[i];
	}
}

bool Pcmp(Point A, Point B) {
	return A.pos < B.pos;
}

void debug() {
	printf("top = %d\n", top);
	for(int i = 1; i <= top; i++)
		printf("%d %d\n", hull[i].x, hull[i].y);
	printf("\n");
}

double prod(Vector A, Vector B) {
	return 1.0 * (A.x * B.x + A.y * B.y);
}

void solve() {
	hull[0] = hull[top];
	hull[top + 1] = hull[1];
	for(int i = 1; i <= top; i++) {
		Vector sa = hull[i - 1] - hull[i];
		Vector sb = hull[i + 1] - hull[i];
		hull[i].pb = (PI - acos(prod(sa, sb) / (dis(sa, Point(0LL, 0LL)) 
		                 * dis(sb, Point(0LL, 0LL))))) / (2.0 * PI);
	}
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= top; j++) {
			if(PP[i] == hull[j]) {
				PP[i].pb = hull[j].pb;
				break;
			}
		}
	}
	sort(PP + 1, PP + n + 1, Pcmp);
	for(int i = 1; i <= n; i++)
		printf("%.15lf\n", PP[i].pb);
}

int main()
{
	//printf("acos() = %lf\n", acos(-0.5));
	while(scanf("%d", &n) != EOF)
	{
		top = 0;
		for(int i = 1; i <= n; i++) {
			scanf("%lld %lld", &PP[i].x, &PP[i].y);
			PP[i].pos = i;
			PP[i].pb = 0.0;
		}
		Graham();
		//debug();
		solve();
	}
	return 0;
}

Measured memory_bytes: 384
import Data.Bool(bool)
import Data.List

readInt :: String -> Int
readInt = read

main = do
    s <- map readInt.words<$>getContents
    if (solve s == 0) then putStrLn "TLE" else print $ solve s 

solve :: [Int] -> Int
solve (n:t:ci) = bool 0 result $ (length cs)>0
 where
  result = minimum cs
  cs = bounded ci
  bounded [] = []
  bounded [c] = [c]
  bounded (c:i:xs) = bool (c:(bounded xs)) (bounded xs) $ i > t

Measured memory_bytes: 892
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> l_l;
typedef pair<int , int> i_i;
typedef vector<ll> vel;
typedef vector<int> vei;
typedef vector<char> vec;
typedef vector<bool> veb;
typedef vector<string> ves;
typedef vector<vector<ll>> ve_vel;
typedef vector<vector<int>> ve_vei;
typedef vector<vector<char>> ve_vec;
typedef vector<vector<bool>> ve_veb;
typedef vector<vector<string>> ve_ves;
#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 rep2(i,n) for(int i=2;i<(int)(n);i++)
#define repk(i,k,n) for(int i=k;i<(int)(n);i++)
#define fs first
#define sc second
#define pub push_back
#define puf push_front
#define pob pop_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define maxel(a) *max_element(all(a))
#define minel(a) *min_element(all(a))
#define acc accumulate
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define mod (1000000007)
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }


ll factorial(int k){
    ll sum = 1;
    for (int i = 1; i <= k; ++i) sum = sum * i % mod;
    return sum;
}

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

    int N,M; cin >> N >> M;
    if(N != M-1 and N != M and N != M+1) {cout << 0 << endl; return 0;}
    
    else if(M == N) {
        cout << 2 * factorial(N) * factorial(M) % mod << endl;
        return 0;
    }
    else {
        cout << factorial(N) * factorial(M) % mod << endl;
        return 0;
    }
}



Measured memory_bytes: 384
#define _CRT_SECURE_NO_WARNINGS
//#include <stdafx.h>
//#include "targetver.h"
#include <stdio.h>
//#include <tchar.h>
#include <iostream>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif>

#define LL long long
#define MOD 1000000007
#define INF 1000000000
#define LINF 10000000000000000

using namespace std;

const int N = 5e3 + 10;

LL a[N];
LL b[N];
LL pr[N];
LL dp[N][N];
vector<int>vec;
LL n;
LL solve(LL l, LL r) {

	if (l == r)
		return a[l];

	if (dp[l][r] != 0)
		return dp[l][r];

	LL p1 = a[l] + ((pr[r] - pr[l]) - solve(l + 1, r));
	LL p2 = a[r] + ((pr[r - 1] - pr[l-1]) - solve(l, r - 1));
	
	dp[l][r] = max(p1, p2);
	return dp[l][r];
}


int main() {

	scanf("%lld", &n);

	for (int i = 1; i <= n; i++) {

		scanf("%lld", &a[i]);
		pr[i] = pr[i - 1] + a[i];
	}
	LL x = solve(1, n);
	cout << x - (pr[n] - x);

	//cin >> n;
}

Measured memory_bytes: 118528
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <queue>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <complex>
#include <cstdint>
#include <tuple>
#include <numeric>
#define M_PI       3.14159265358979323846


using namespace std;

//conversion
//------------------------------------------
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
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define MT make_tuple
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define FILL(a, x) memset(a, x, sizeof(a))

//repetition
//------------------------------------------
#define FOR(i,s,n) for(int i=s;i<(int)n;++i)
#define REP(i,n) FOR(i,0,n)

int main() {
	string s;
	cin >> s;
	int n = s.length();
	REP(i, n - 1) {
		if (s[i] == s[i + 1]) {
			printf("Bad\n");
			return 0;
		}
	}
	printf("Good\n");
	return 0;
}

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

#define Omar45 ios_base::sync_with_stdio(false); cin.tie(NULL);
#define ll long long
#define pb push_back
#define F first
#define S second
#define endl '\n'
#define mod 1e9 + 7
const ll maxN = 3000 + 5;
const int INF = 0x3f3f3f3f;

string s, t;
int dp[maxN][maxN];
vector <char> stringy;

void printSub(int x, int y){
    while (x && y) {
        if (s[x-1] == t[y-1]) {
            stringy.pb(s[x-1]);
            x--; y--;
        }
        else {
            if (dp[x][y-1] >= dp[x-1][y])
                y--;
            else if (dp[x][y-1] < dp[x-1][y])
                x--;
        }
    }
    for (int i=stringy.size()-1; i>=0; i--)
        cout << stringy[i];
}

int main() {
	Omar45
    cin >> s >> t;
    int N = s.size();
    int M = t.size();
    for (int i=0; i<=N; i++)
        dp[i][0] = 0;
    for (int i=0; i<=M; i++)
        dp[0][i] = 0;
    for (int i=1; i<=N; i++){
        for (int j=1; j<=M; j++){
            if (s[i-1]==t[j-1])
                dp[i][j] = dp[i-1][j-1]+1;
            else
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    }
    printSub(N,M);
}


Measured memory_bytes: 35456
#include <iostream>
#include <iomanip> // << fixed << precision(10)
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cmath>
#include <algorithm>
using namespace std;

#define FOR(i,s,t) for(int i=s;i<t;i++)
#define REP(i,n) FOR(i,0,n)
#define PRINT(s) cout << s << "\n"
#define SORT(A) sort(A.begin(), A.end())
#define EACHPRINT(A, T) for_each(begin(A), end(A), [&](T i){ cout << i << " "; });cout << "\n"
#define NEWMAT(N, M, ini) MAT(N, vector<lint>(M, ini))
#define MOD 1000000007

typedef long long lint;
typedef pair<lint, lint> P;
typedef vector<lint> V;
typedef vector<vector<lint>> MAT;
bool lessPair(const P& l, const P& r){return l.second < r.second;}

struct UnionFind {
  vector<lint> par;
  vector<lint> weight;

  UnionFind(int N) : par(N), weight(N) {
    for(int i = 0; i < N; i++) {
      par[i] = i;
      weight[i] = 1;
    }
  }
  
  int root(lint x) {
    if (par[x] == x) return x;
    return par[x] = root(par[x]);
  }

  void unite(lint x, lint y) {
    lint rx = root(x);
    lint ry = root(y);
    if (rx == ry) return;
    weight[ry] = weight[rx] + weight[ry];
    par[rx] = ry;
  }

  bool same(lint x, lint y) {
    lint rx = root(x);
    lint ry = root(y);
    return rx == ry;
  }

  lint get_weight(lint x) {
    return weight[root(x)];
  }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    lint N; cin >> N;
    lint M; cin >> M;

    V res(M);

    UnionFind uni(N);
    vector<P> E(M);

    lint current = N*(N-1)/2;
    
    REP(i, M) {
      lint x; cin >> x;x--;
      lint x2; cin >> x2;x2--;
      E[i] = P(x,x2);
    }

    REP(i, M) {
      res[M-i-1] = current;

      lint x = E[M-i-1].first;
      lint x2 = E[M-i-1].second;

      if(!uni.same(x,x2)) {
        current -= uni.get_weight(x) * uni.get_weight(x2);
        //        cout << x << " weight:" << uni.get_weight(x)
        //              << " " << x2 << " weight:" << uni.get_weight(x2) << "\n";
      }

      uni.unite(x, x2);
    }

    REP(i, M) {
      PRINT(res[i]);
    }

    return 0;
}


Measured memory_bytes: 5248
/*まずうちさあ屋上あんだけど、焼いてかない？*/
	#include <bits/stdc++.h>
	using namespace std;
	#define IOS ios::sync_with_stdio(false), cin.tie(0)
	#define REP(i, n) for (int i = 0; i < n; i++)
	#define FOR(i, a, b) for (int i = a; i < b; i++)
	#define ALL(x) (x).begin(), (x).end()
	#define dump(x) cout << (x) << endl
	#define LMAX 9223372036854775807LL
	#define LMIN -9223372036854775807LL

	using ll = long long;
	template<typename T>
	using vec = vector<T>;
	using P = pair<ll, ll>;

	template <typename A, size_t N, typename T>
	void Fill(A (&array)[N], const T &val){
		fill((T *)array, (T *)(array + N), val);
	}
	
	ll pas[51][52];
	const ll INF = 1e18;
	const ll mod = 1e9 + 7;

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

	
	bool f[100][10];
	ll p[100][11];
	int main(){
		IOS;
		int n;
		cin >> n;		
		REP(i,n)REP(j,10)cin >> f[i][j];
		REP(i,n)REP(j,11)cin >> p[i][j];
		vec<ll> a(n,0);
		vec<bool> op(10,false);
		ll ans = LMIN;
		for(int i = 1;i < (1 << 10);i++){
			ll tmp = 0;
			int j = i;
			REP(k,10){
				op[k] = j % 2;
				j /= 2; 
			}
			REP(k,n){
				ll cnt = 0;
				REP(l,10)if(op[l] && f[k][l])cnt++;
				tmp += p[k][cnt];
			}
			ans = max(tmp,ans);
		}
		dump(ans);
	}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <cmath>
#include <cstdlib>
#include <climits>
using namespace std;

int main(){
  string a,b,c;

  cin >> a >> b >> c;

  if(a[a.size()-1] == b[0] && b[b.size() - 1] == c[0]){
    cout << "YES" << endl;
  }else{
    cout << "NO" << endl;
  }

  return 0;
}

Measured memory_bytes: 256
#include <fstream>
#include <iostream>
#include <string>
#include <iterator>
#include <stdlib.h>
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll=long long;
inline constexpr ll gcd(ll a,ll b){if(!a||!b)return 0;while(b){ll c=b;b=a%b;a=c;}return a;}
inline constexpr ll lcm(ll a,ll b){if(!a||!b)return 0;return a*b/gcd(a,b);}
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
int main(){
  int a;
  cin>>a;
  long long sum=0;
  rep(i,a){
      rep(j,a){
          rep(k,a){
              sum+=gcd(gcd(i+1,j+1),k+1);
          }
      }
  }
  cout<<sum<<endl;
}

Measured memory_bytes: 3636
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <map>
#include <numeric>
#include <random>
using namespace std;

int gcd(int a, int b) {
	if (b == 0) {
		return a;
	}
	return gcd(b, a % b);
}

int gcd_of_vector(vector<int> A, int begin, int end){
  int result = A[begin];
  for(int i=begin;i<end;i++){
    result = gcd(A[i],result);
  }
  return result;
}

int gcd_of_vector_with_skip(vector<int> A, int skip){
  int result = A[0];
  if(skip==0)result=A[1];
  for(int i=1;i<A.size();i++){
    if(i==skip)continue;
    result = gcd(A[i],result);
  }
  return result;
}

int main()
{
  int N,ans,gcd1,gcd2;
  cin>>N;
  vector<int> A(N);
  for(int i=0;i<N;i++){
    cin>>A[i];
  }

  if(N>=10){
    ans=1000000010;
    for(int i=0;i<1;i++){
      random_shuffle(A.begin(),A.end());
      gcd1 = gcd_of_vector(A,0,N/2);
      gcd2 = gcd_of_vector(A,N/2,N);
      ans = min(ans,max(gcd1,gcd2));
    }
  }else{
    ans=0;
    for(int i=0;i<N;i++){
      ans=max(ans,gcd_of_vector_with_skip(A,i));
    }
  }

  cout<<ans<<endl;
}


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

#define rep(i, n) for(int (i) = 0; (i) < (n); (i)++)
#define repn(i, n) for(int (i) = 1; (i) <= (n); (i)++)
#define repr(i, n) for(int (i) = (n-1); (i) >= 0; (i)--)
#define all(x) (x).begin(), (x).end()
#define lint long long
#define ulint unsigned long long
#define fi first
#define se second
#define setpre(x) cout << fixed << setprecision(x)
#define ii(x) int x; cin >> (x)
#define ii2(x, y) int x, y; cin >> (x) >> (y)
#define ii3(x, y, z) int x, y, z; cin >> (x) >> (y) >> (z)
#define out(x) cout << (x) << endl
#define outs(x) cout << (x) << " "
#define yn(x) cout << ((x)?("Yes"):("No")) << endl
#define YN(x) cout << ((x)?("YES"):("NO")) << endl
#define bit_c(x) __builtin_popcountll(x)

inline void logger(){ cout << " [LOGGER] " << endl; }
template<typename A, typename... B>
void logger(const A& a, const B&... b){
    cout << a << " , ";
    logger(b...);
}

typedef pair<lint, lint> P;
const lint MOD = 1000000007;
const lint MOD9 = 998244353;
const lint INF = MOD * MOD;
const int MAX = 200005;

/* ...o(^-^)o... */

int main(){
    lint a, b, c; cin >> a >> b >> c;
    lint d = c-a-b;
    if(d > 0 && 4*a*b < d*d){
        out("Yes");
    }
    else{
        out("No");
    }
}


Measured memory_bytes: 256
#include <stdio.h>

int main() {
    // insert code here...
    int n;
    int x[1000];
    int y;
    int h, i, j, k;
    int di, an;
    for(;;){
        scanf("%d", &n);
        if(n == 0) break;
        else{
            for(h = 1; h < n + 1; h++){
                scanf("%d", &x[h]);
            }
            for(i = 2; i < n + 1; i++){
                j = i - 1;
                while(j > 0 && x[j] > x[j+1]){
                    y = x[j+1];
                    x[j+1] = x[j];
                    x[j] = y;
                    j = j - 1;
                }
            }
            an = 1000000;
            for(k = 1; k < n; k++){
                di = x[k+1] - x[k];
                if(an > di) an = di;
            }
            
            printf("%d\n", an);
        }
    }
    return 0;
}


Measured memory_bytes: 2616
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N = ii()
    ans = INF
    for i in range(1,11):
        yen = i * 1000
        c = yen-N
        if c >= 0:
            ans = min(ans,c)
        
    print(ans)



if __name__ == "__main__":
    main()

Measured memory_bytes: 61800
using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApp13
{
    class Program
    {
        static void Main(string[] args)
        {
            string A = Console.ReadLine();
            int a = int.Parse(A);
            var x = Console.ReadLine().Split(' ');
            var z = new List<double>();
           for(int b = 0; b < a; b++)
            {
                double y = double.Parse(x[b]);
                z.Add(y);
            }
            z.Sort();
            double v = z.Sum();
            double w = z.Last();
            double u = z.First();
            Console.WriteLine("{0} {1} {2}",u,w,v);
        }
    }
}

Measured memory_bytes: 11004
import java.util.*;
public class Main {
	public static void myout(Object text){//standard output
		System.out.println(text);
	}
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		//String tmp = sc.next();
		//int tmp = sc.nextInt();
		//Long tmp = sc.nextLong();
      int len = sc.nextInt();
      Long output = new Long(1);
      int[] checked = new int[len];
      Arrays.fill(checked,0);
      while(sc.hasNext()){
        int tmp = sc.nextInt();
        checked[tmp]++;
      }
      for(int i = (len - 1) % 2; i <= len - 1; i += 2){
        if(i == 0 && checked[i] != 1){
          myout("0");
          return;
        }else if(i != 0 && checked[i] != 2){
          myout("0");
          return;
        }else{
       		output = (output * checked[i]) % 1000000007;
        }
      }
      
      myout(output);
	}
}


Measured memory_bytes: 58864
#include<iostream> 
#include<vector>
using namespace std; 
typedef long long ll; 
int main() 
{ 
		ios::sync_with_stdio(false); 
		cin.tie(NULL);  
		int n;
		cin>>n; 
		vector<int> arr; 
		arr.assign(n,0);
		int input;
		int prev; 
		cin>>prev;
		arr[prev-1]++;
		for(int i=0; i<n-2; i++) 
		{ 
				cin>>input; 
				if(prev==input) 
					arr[prev-1]++;
				else
				{ 
						prev=input; 
						arr[prev-1]++;
				}
		}  
		for(int i=0; i<n; i++) 
		{ 
				cout<<arr[i]<<"\n"; 
		}
		return 0; 
}


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

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int MOD = 998244353;

ll gcd(ll a, ll b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

int main() {
    /*ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);*/
    
    ll n;
    cin >> n;
    
    string ans = "";
    while (n > 0) {
        --n;
        char cur = 'a' + (n % 26);
        ans = cur + ans;
        n /= 26;
    }
    cout << ans << "\n";
    
    return 0;
}


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

main()
{
  char str[21];
  int i,len;

  scanf("%s",str);
  len=strlen(str)-1;
 

  for(i=len;i>=0;i--){
    printf("%c",str[i]);
  }
printf("\n");
  return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define rt return 0
#define endln "\n"
#define all(v) v.begin(), v.end()
#define for1(i, a, b) for (long long int i = a; i < b; i++)
#define for2(i, a, b) for (long long int i = a; i > b; i--)
//  cout << fixed << setprecision(0) << pi <<" "<<npi<<endl;typedef long long int i;
typedef long long int lli;
typedef pair<lli, lli> pll;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    lli n, x, m;
    cin >> n >> x >> m;
    vector<lli> v(m + 2);
    vector<lli> summ(m + 2);

    // vector<lli>()
    map<lli, lli> ma;
    if (n <= m)
    {
        lli a = x;
        for1(i, 1, n)
        {
            x *= x;
            x %= m;
            a += x;
        }
        cout << a << endl;
        return 0;
    }
    v[1] = x % m;
    summ[1] = v[1];
    lli f1, f2;
    for1(i, 2, m + 2)
    {
        v[i] = v[i - 1];
        v[i] *= v[i - 1];
        v[i] %= m;
        summ[i] = v[i] + summ[i - 1];
        // summ[i] %=
        if (ma[v[i]] != 0)
        {
            f2 = i, f1 = ma[v[i]];
            break;
        }
        ma[v[i]] = i;
    }
    // cout << f2 << " " << f1 << " " << summ[f2] << endl;
    lli r = f2 - f1;
    lli left = n - f2;
    lli mul = left / r;
    lli rem = left % r;

    lli rec = summ[f2] - summ[f1];
    // rec %= m;
    rec *= mul;
    // rec %= m;
    summ[f2] += rec;
    // summ[f2] %= m;
    lli ans = summ[f2];
    lli prev = v[f2];
    // cout << prev << endl;
    // cout << n - rem + 1 << " " << n << endl;
    for (lli i = n - rem + 1; i <= n; i++)
    {
        // cout << i << endl;
        prev *= prev;
        prev %= m;
        ans += prev;
        // ans %= m;
        // cout << prev << endl;
    }
    cout << ans << endl;
}

Measured memory_bytes: 7876
#include <bits/stdc++.h>
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((int)(x).size())
#define re(n) for (int i = 0; i < (n); ++i)
#define rej(n) for (int j = 0; j < (n); ++j)

using namespace std;

typedef long long ll;
typedef long double ld;
typedef vector <int> vi;
typedef pair <int, int> pii;
typedef vector <pair <int, int>> vii;

const ld PI = acos((ld)-1);

int main() {
    #ifndef LOCALDEBUG
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    #endif  // LOCALDEBUG
    int n;
    string s;
    cin >> n >> s;
    int ans = 0;
    char cur = 0;
    re(n) {
        if (s[i] != cur) {
            cur = s[i];
            ++ans;
        }
    }
    cout << ans;
    return 0;
}


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

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

int main()
{
    int A, B, C;

    cin >> A >> B >> C;
    if((A <= C && C <= B) || (B <= C && C <= A)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}


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

if a == 0:
    print(0)
elif a+b >= n:
    print(a) if a <= n else print(n)
else:
    ab = a + b
    ans = n // ab * a
    ans += a if n % ab > a else n % ab 
    print(ans)

Measured memory_bytes: 3060
#include<iostream>
#include<cstdio>

using namespace std;

int main(void)
{
	int num;
	double weight, height, bmi;
	
	while(scanf("%d,%lf,%lf", &num, &weight, &height) != EOF ){
		bmi = weight / (height * height);
		if(bmi >= 25)
		cout << num << endl;
	}
	return 0;
}

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

int main() {
    int n, x, cnt, ans=300000;
    string s;
    cin >> n >> s;
    vector<int> a(n), b(n);
    

    cnt=0;
    for(int i=0;i<n; i++) {
        a[i]=cnt;
        if(s.at(i)=='W') cnt++;
    }

    cnt=0;
    for(int i=n-1;i>=0; i--) {
        b[i]=cnt;
        if(s.at(i)=='E') cnt++;
    }

    for(int i=0; i<n; i++) {
        ans=min(ans, a[i]+b[i]);
    }

    cout << ans;
}

Measured memory_bytes: 2948
mod = 10**9+7
N, K = map(int, input().split())
a = list(map(int, input().split()))
dp = [0]*(K+1)

for i in range(a[0]+1):
    dp[i] = 1
for i in range(1, N):
    S = [0]*(K+2)
    for j in range(1, K+2):
        S[j] = S[j-1]+dp[j-1]
        S[j]%=mod
    for j in range(K+1):
        dp[j] = (S[j+1]-S[max(0, j-a[i])])%mod
print(dp[-1])






Measured memory_bytes: 64952
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
typedef long long ll;
typedef pair<int, int> P;
const int INF = 100100100;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;
ll calc(ll x,ll y){
  if(x<y){
    return y - x;
  }else if(x==y){
    return 0;
  }
  return 1e10;
}
int main()
{
  ll x, y;
  cin >> x >> y;
  ll cnt = 0;
  cnt = min(calc(x, y), calc(-x, y) + 1);
  ll cnt2 = min(calc(x, -y) + 1, calc(-x, -y) + 2);
  cnt = min(cnt, cnt2);
  cout << cnt << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define For(i,x,y) for (register int i=(x);i<=(y);i++)
#define FOR(i,x,y) for (register int i=(x);i<(y);i++)
#define Dow(i,x,y) for (register int i=(x);i>=(y);i--)
#define Debug(v) for (auto i:v) printf("%lld ",i);puts("")
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define ep emplace_back
#define siz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define fil(a,b) memset((a),(b),sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pa;
typedef pair<ll,ll> PA;
typedef vector<int> poly;
inline ll read(){
    ll x=0,f=1;char c=getchar();
    while ((c<'0'||c>'9')&&(c!='-')) c=getchar();
    if (c=='-') f=-1,c=getchar();
    while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x*f;
}

const int N = 310, mod = 998244353;
int n,k,dp[N][2*N][N],cnt,p[N],a[N];
char s[N];

inline void upd(int &x,int y){
	x+=y;
	if (x>=mod) x-=mod;
}

int main(){
	scanf("%s%d",s+1,&k),n=strlen(s+1);
	For(i,1,n) if (s[i]=='0') p[++cnt]=i;
	For(i,1,cnt) a[i]=p[i]-p[i-1]-1;
	a[cnt+1]=n-p[cnt],k=min(k,(n-cnt));
	dp[0][0][0]=1;
	For(i,0,cnt-1) For(j,0,n-cnt) For(l,0,k) if (dp[i][j][l]){
		For(p,0,n-cnt) if (j+p-a[i+1]>=0) upd(dp[i+1][j+p-a[i+1]][l+max(0,a[i+1]-p)],dp[i][j][l]); 
	}
	int ans=0; 
	For(i,0,a[cnt+1]) For(j,0,k-i) upd(ans,dp[cnt][i][j]);
	printf("%d\n",ans);
}

Measured memory_bytes: 58592
#include <bits/stdc++.h>
#define REP(a, b) for(int a = 0; a < b; a++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define mp make_pair
#define f first
#define s second
#define pb push_back
using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ll, ll> LL;
typedef vector<int> vi;

const ll INF = 1e9;
const ll MOD = 1e9 + 7;
const int MAXN = 3005;

string s, t;
int DP[MAXN][MAXN];
ii langkah[MAXN][MAXN];

int rek(int a, int b) {
	if (a == s.size() || b == t.size()) return 0;
	int &ret = DP[a][b];
	if (ret != -1) return ret;
	if (s[a] == t[b]) {
		langkah[a][b] = mp(a + 1, b + 1);
		return ret = 1 + rek(a + 1, b + 1);
	}
	ret = max(rek(a + 1, b), rek(a, b + 1));
	if (rek(a + 1, b) == ret) langkah[a][b] = mp(a + 1, b);
	else langkah[a][b] = mp(a, b + 1);
	return ret;
}

int main() {
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	ios::sync_with_stdio(0); cin.tie(0);
	memset(DP, -1, sizeof DP);
	cin >> s >> t;
	int a = 0, b = 0;
	rek(0, 0);
	while(a < s.size() && b < t.size()) {
		if (langkah[a][b] == mp(a + 1, b + 1)) cout << s[a];
		ii now = langkah[a][b];
		a = now.f, b = now.s;
	}
	cout << '\n';
}	

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

int main(){
  string s;
  cin >> s;
  ll k;
  cin >> k;
  k--;
  int n=s.size();
  int ans=1;
  for(int i=0;i<n;++i){
    if(i<=k && s[i]!='1'){
      ans=int(s[i]-'0');
      break;
    }
  }
  cout << ans << endl;
  return 0;
}


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

int main(int argc, char const *argv[])
{
	long long n,k;
	cin>>n>>k;
	long long ans=(n/k)*(n/k)*(n/k);
	if (k%2LL==0LL)
	{
		ans+=((n+k/2LL)/k)*((n+k/2LL)/k)*((n+k/2LL)/k);
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 256
function main()
  
  (X,Y) = map(x -> parse(Int,x), split(readline()))
  
  ans1 = 0
  ans2 = 0
  
  if 4 > X
    ans1 = 100000*(4-X)
  end
  
  if 4 > Y
    ans2 = 100000*(4-Y)
  end
  
  if X == 1 && Y == 1
    println(1000000)
  else
    println(ans1+ans2)
  end
  
end

main()

Measured memory_bytes: 109856
s = input()
count = 0
lens = []

for i, _ in enumerate(s):
  for c in s[i:]:
    if c in ['A', 'G', 'C', 'T']:
      count += 1
    else:
      break
  lens.append(count)
  count = 0
  
print(max(lens))
  


Measured memory_bytes: 9108
#include <iostream>
#define int long long

using namespace std;

const int Num = 2e5 + 10;
const int Mod = 1e9 + 7;

int a[Num];

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

    int sum = 0;
    for (int i = 1; i <= n; ++i)
      cin >> a[i], sum += a[i];

    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        sum -= a[i];
        ans += a[i] * (sum % Mod);
        ans %= Mod;
    }

    cout << ans << '\n';

    return 0;
}



Measured memory_bytes: 5184
#include<algorithm>
#include<complex>
#include<ctype.h>
#include<iomanip>
#include<iostream>
#include<map>
#include<math.h>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<stdio.h>
#include<string>
#include<string>
#include<vector>

using namespace std;
typedef long long ll;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<endl
#define p2(s, t) cout << (s) << " " << (t) << endl
#define pn(s) cout << (#s) << " " << (s) << endl

const ll mod = 1e9 + 7;
const ll inf = 1e18;

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

    // input
    int N;
    cin >> N;

    N--;

    vector<ll> C(N);
    vector<ll> S(N); // ceremony wait
    vector<ll> F(N);
    FOR(i, 0, N){
        cin >> C.at(i);
        cin >> S.at(i);
        cin >> F.at(i);
    }

    FOR(i, 0, N){
        ll t = S[i] + C[i];
        
        // 2つ目以降の駅
        FOR(j, i+1, N){
            // セレモニーは待たなくていい場合
            if(t >= S[j]){
                // すぐ乗れる
                if(t % F[j] == 0){
                    t += C[j];
                }
                // ちょっと待つ
                else{
                    ll waitTime = F[j] - t % F[j];
                    t += C[j] + waitTime;
                }
            }
            // セレモニーを待ち、その後、乗る
            else{
                t = S[j] + C[j];
            }
        }
        p(t);
    }
    p(0);
    
    return 0;
}

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

int n,s[9],cnt;

void make753(int a,int b){
    if(a>b){
        int m=0;
        bool ok7=false,ok5=false,ok3=false;
        for(int i=0;i<=b;i++){
            m*=10;
            m+=s[i];
            if(s[i]==7){
                ok7=true;
            }else if(s[i]==5){
                ok5=true;
            }else {
                ok3=true;
            }
        }
        if(ok7&&ok5&&ok3&&m<=n)cnt++;
        return;
    }
    s[a]=7;
    make753(a+1,b);
    s[a]=5;
    make753(a+1,b);
    s[a]=3;
    make753(a+1,b);
}

int main(){
    cin>>n;
    cnt=0;
    for(int i=0;i<9;i++){
        make753(0,i);
    }
    cout<<cnt<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
#include <functional>
using namespace std;

#define REP(i,n) for(int i=0; i<n; ++i)
#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 ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<double> VD;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef vector<VD> VVD;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

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

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }

int main(void){
    ll n, k;
    cin >> n >> k;
    VL p(n), a(n);
    REP(i,n) p[i] = in() - 1;
    REP(i,n) a[i] = in();

    ll ans = -1e18;
    REP(i,n){
        // cout << "start " << i << endl;
        VI c(n, -1), b;
        int x = i;
        ll r = k, s = 0, z = -1;
        REP(t,k){
            r--;
            x = p[x];
            b.push_back(a[x]);
            s += a[x];
            chmax(ans, s);
            if (c[x] != -1){
                z = c[x];
                break;
            }
            c[x] = t + 1;
        }
        if (r == 0) continue;
        VL d;
        FOR(j,z,b.size()-1) d.push_back(b[j]);
        ll m = d.size();
        ll sd = 0;
        for (ll x : d) sd += x;
        // REP(j,m) cout << d[j] << " ";
        // cout << " " << sd << endl;
        // cout << r << " " << s << endl;
        if (sd > 0){
            s += sd * (r / m);
            // cout << s << endl;
            chmax(ans, s);
            r %= m;
            REP(j,r){
                s += d[j];
                chmax(ans, s);
            }
        }
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3872