akhauriyash/Code-Regression huggingface dataset:
#from statistics import median
import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
#from fractions import gcd
#from itertools import combinations # (string,3) 3回
#from collections import deque
#from collections import deque,defaultdict
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())

S = input()
ln = len(S)
ans = [0] * (ln+1)
# 前から
for i in range(ln):
    if S[i] == '<':
        ans[i+1] = max(ans[i+1],ans[i]+1)
#print(ans)
# 後ろから
for i in range(ln-1,-1,-1):
    if S[i] == '>':
        ans[i] = max(ans[i],ans[i+1]+1)
#print(ans)
print(sum(ans))


Measured memory_bytes: 23724
package main

import (
	"fmt"
	"strings"
)

func main() {
	var S string
	fmt.Scan(&S)
	if S[0] == 'A' && strings.Count(S, "A") == 1 && strings.Count(S, "C") == 1 &&
		strings.Count(S[2:len(S)-1], "C") == 1 && !strings.ContainsAny(S, "BDEFGHIJKLMNOPQRSTUVWXYZ") {
		fmt.Println("AC")
		return
	}
	fmt.Println("WA")
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 3e5 + 5, mod = 1e9 + 7;

vector<int> adj[N];
int dis[N];

void bfs(int src){
    memset(dis, -1, sizeof dis);
    dis[src] = 0;
    queue<int> q;
    q.push(1);
    while(q.size()){
        int node = q.front();
        q.pop();
        for(auto i: adj[node]){
            if(dis[i] == -1){
                dis[i] = node;
                q.push(i);
            }
        }
    }
}


int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    bfs(1);
    cout << "Yes\n";
    for(int i = 2; i <= n; i++) cout << dis[i] << '\n';


    return 0;

}


Measured memory_bytes: 16012
#include<iostream>
#include<vector>
#include<set>
#include<unordered_set>
#include<list>
#include<stack>
#include<queue>
#include<map>
#include<unordered_map>
#include<algorithm>
#include<cmath>
#include<tuple>
#include<iomanip>
#include<climits>
#define ll long long int
#define mod 1000000007
#define pi acos(-1)
using namespace std;

ll fastPower(ll a, ll b, int m)
{ 
	if(b==0)
	    return 1;
	ll res = fastPower( a , b/2 ,  m);
	res = (res*res)%m;
	if(b%2==1)
	{
		res = ((res%m)*(a%m))%m;
	}
	return  res;
}

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  ll n, a, b;
  cin>>n>>a>>b;
  ll ans = fastPower(2, n , mod);
  ans--;
  ll prod = 1;
  ll prod2=1;
  for(int i=n;i>max(a, n-a);i--)
  {
    prod*=i;
    prod%=mod;
  }
  for(int i=1;i<=min(a,n-a);i++ )
  {
    prod2*=i;
    prod2%=mod;
  }
  prod = (prod*(fastPower(prod2,mod-2,mod)))%mod;
  ans -= prod;
  prod=1;
  prod2=1;
  for(int i=n;i>max(b, n-b);i--)
  {
    prod*=i;
    prod%=mod;
  }
  for(int i=1;i<=min(b,n-b);i++ )
  {
    prod2*=i;
    prod2%=mod;
  }
  prod = (prod*(fastPower(prod2,mod-2,mod)))%mod;
  ans -= prod;

  cout<<(ans+2*mod)%mod;
  return 0;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
template <typename T> vector<vector<T>> make_vector_2d(int n, int m, T initialValue) {
    auto r = vector<vector<T>>(n);
    for (int i = 0; i < n; i++) r[i] = vector<T>(m,initialValue);
    return r;
}
template <typename T> vector<vector<vector<T>>> make_vector_3d(int n, int m, int l, T initialValue) {
    auto r = vector<vector<vector<T>>>(n);
    for (int i = 0; i < n; i++) {
        r[i] = vector<vector<T>>(m);
        for (int j = 0; j < m; j++) r[i][j] = vector<T>(l, initialValue);
    }
    return r;
}

int main() {

    string s;
    cin >> s;
    if (s[2] == s[3] && s[4] == s[5]) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }

    return 0;

}


Measured memory_bytes: 256
#include<stdio.h>

int main(void){
	double a[3], b[3], c[3], d[3], e[3], f[3];
	double x, y;

	while (scanf("%lf %lf %lf %lf %lf %lf",&a[0],&b[0],&c[0],&d[0],&e[0],&f[0]) != EOF){
		
		a[1] = a[0] * e[0];
		b[1] = b[0] * e[0];
		c[1] = c[0] * e[0];
		d[1] = d[0] * b[0];
		e[1] = e[0] * b[0];
		f[1] = f[0] * b[0];

		x = (c[1] - f[1]) / (a[1] - d[1]);
		if (x == -0) x = 0;
		a[2] = a[0] * d[0];
		b[2] = b[0] * d[0];
		c[2] = c[0] * d[0];
		d[2] = d[0] * a[0];
		e[2] = e[0] * a[0];
		f[2] = f[0] * a[0];

		y = (c[2] - f[2]) / (b[2] - e[2]);
		if (y == -0) y = 0;
		printf("%.3f %.3f\n", x, y);

	}
	return 0;
}

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

using namespace std;
using ll =long long;
typedef pair<int,int> P;
#define SORT(a) sort((a).begin(),(a).end())
#define REV(a) reverse((a).begin(),(a).end())
#define For(i, a, b)    for(int i = (a) ; i < (b) ; ++i)
#define rep(i, n)       For(i, 0, n)
#define debug(x)  cerr << #x << " = " << (x) << endl;
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; }

void coY() {cout <<"Yes"<<endl;}
void coN(){cout <<"No"<<endl;}
 
//Write From this Line

//const ll mod = 1e9+7;
//const ll mod = 998244353;

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

// Binary Indexed Tree (Fenwick Tree)
// https://youtu.be/lyHk98daDJo?t=7960
template<typename T>
struct BIT {
  int n;
  vector<T> d;
  BIT(int n=0):n(n),d(n+1) {}
  void add(int i, T x=1) {
    for (i++; i <= n; i += i&-i) {
      d[i] += x;
    }
  }
  T sum(int i) {
    T x = 0;
    for (i++; i; i -= i&-i) {
      x += d[i];
    }
    return x;
  }
  T sum(int l, int r) {
    return sum(r-1) - sum(l-1);
  }
};
int main()
{
	int n, q;
	cin >> n >> q;
	vector<int> a(n);
	rep(i, n)cin>>a[i];

	vector<int> pi(n+1, -1);
	vector<vector<int>> ps(n);
	rep(i,n){
		int l = pi[a[i]];
		if(l != -1){
			// 赤矢印として登録する
			ps[l].push_back(i);
		}
		pi[a[i]] = i;
	}
	vector<vector<P>> qs(n);
	rep(qi, q){
		int l, r;
		cin >> l >> r;
		l--, r--; // 0-indexed
		qs[l].emplace_back(r,qi);
	}
	BIT<int> d(n);
	vector<int> ans(q);
	for(int x = n - 1; x >= 0; x--){
		for(int y: ps[x]) d.add(y,1);
		for(P query : qs[x]) {
			int r = query.first, i = query.second;
			ans[i] = r - x  + 1 - d.sum(r);
		}
	}
	rep(i,q) cout << ans[i] << endl;
}


Measured memory_bytes: 59884
//Bismillahir Rahmanir Raheem
//In the name of Allah , Most Gracious , Most Merciful

/*

  * * * * * * *   * * * * * * *   *           *   * * *   * * * * * *
              *   *           *   *           *     *     *           *
              *   *           *   *           *     *     *             *
              *   *           *   *           *     *     *             *
              *   * * * * * * *   * * * * * * *     *     *             *
  *           *   *           *   *           *     *     *             *
  *           *   *           *   *           *     *     *             *
  *           *   *           *   *           *     *     *           *
  * * * * * * *   *           *   *           *   * * *   * * * * * *

*/

#include<bits/stdc++.h>
using namespace std;

#define BOOST ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define DEBUG freopen("input.txt","r",stdin)


int main()
{
    BOOST;
    //DEBUG;
    int n,c=0;
    cin>>n;

    vector<int> v1(n+1,0);
    for(int i=0; i<n-1; i++)
    {
        int x;
        cin>>x;
        v1[x]++;
    }
    for(int i=1; i<=n; i++)
    {
        cout<<v1[i]<<endl;
    }




    return 0;
}





Measured memory_bytes: 3992
n,a,b=gets.split.map(&:to_i)
s=gets
all=0
bb=0
n.times {|i|
    if s[i] == 'c'
        puts :No
    elsif s[i] == 'a'
        if all < a + b
            puts :Yes
            all += 1
        else
            puts :No
        end
    else
        if all < a + b and bb < b
            puts :Yes
            all += 1
            bb += 1
        else
            puts :No
        end
    end
}


Measured memory_bytes: 2300
#include <bits/stdc++.h>
#include <string>
using namespace std;
 
int main() {
  string s;
  int d[3];
  int count = 0;
  cin >> s;
  for (int i=0; i<3; i++) {
    d[i] = atoi(s.substr(i,1).c_str());
    if(d[i] == 1) {
      count += 1;
    }
  }
  cout << count << endl;
}

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

if n == 1:
    print(a[0])
    exit()

b = list(sorted(set(a)))

def count_inversion(ans):
    s = [0 for _ in range(2 * n + 2) ]

    def bit_add(i):
        x = i
        while x < 2 * n:
            s[x] += 1
            x += x & -x

    def bit_sum(i):
        x = i
        ret = 0
        while x > 0:
            ret += s[x]
            x -= x & -x
        return ret

    temp = [n for _ in range(n + 1)]
    temp[0] = n + 1
    for i in range(n):
        if a[i] >= b[ans]:
            temp[i + 1] = temp[i] + 1
        else:
            temp[i + 1] = temp[i] - 1
    res = 0
    for i in range(n + 1):
        x = temp[i]
        res += bit_sum(x)
        bit_add(x)
    return res

m = n * (n + 1) // 2

ans = 0

l = 0
r = len(b)
while 1:
    ans = (l + r) // 2
    if count_inversion(ans) * 2 >= m:
        l = ans
    else:
        r = ans
    if r - l <= 1:
        ans = l
        break

print(b[ans])


Measured memory_bytes: 124212
import java.util.*;

class Main {
    public static void main(String[] args) throws Exception{
	    Scanner sc = new Scanner(System.in);
		long N=sc.nextLong();
		sc.close();
		String t="";
		while(N>0){
		    N--;
		    t+=(char)('a'+N%26);
		    N/=26;
		}
		for(int i=t.length()-1;i>=0;i--) {
			System.out.print(t.charAt(i));
		}
	}
}


Measured memory_bytes: 39284
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<string>
#include<cstdio>
#include<cstring>
#include<iomanip>
#include<iostream>
#include<algorithm>
#define INF 0x3f3f3f3f
#define LL long long
using namespace std;
const int maxn=555;

int main(){
    char s[30];
    int vis[30];
    memset(vis,0,sizeof(vis));
    scanf("%s",s);
    int len=strlen(s);
    for(int i=0;i<len;i++)
        vis[s[i]-'a']=1;
    if(strcmp(s,"zyxwvutsrqponmlkjihgfedcba")==0) printf("-1\n");
    else {
        if(len<26){
            printf("%s",s);
            for(int i=0;i<26;i++)
                if(!vis[i]){
                    printf("%c\n",i+'a');
                    break;
                }
        }
        else{
            int k=25;
            for(k=25;k>0;k--){
                if(s[k]>s[k-1]){
                    vis[s[k]-'a']=0;
                    vis[s[k-1]-'a']=0;
                    break;
                }
                vis[s[k]-'a']=0;
            }
            char c=s[k-1];
            if(!k) printf("b\n");
            else {
                s[k-1]='\0';
                printf("%s",s);
                for(int i=c-'a'+1;i<26;i++){
                    if(!vis[i]) {printf("%c\n",i+'a'); break;}
                    //printf("%d\n",i);
                }
            }
        }
    }
    return 0;
}


Measured memory_bytes: 256
n, m = gets.split(" ").map(&:to_i)
cnt = []
res = 0
for i in 0..(n-1) do
  p = gets.split(" ").map(&:to_i)
  cnt << p[1..p[0]]
end
cnt.flatten!

for j in 1..m do
  if cnt.count(j) == n
    res += 1
  end
end

puts res

Measured memory_bytes: 1788
#include <bits/stdc++.h>
#include <cstdio>
#define fastio {ios_base::sync_with_stdio(false); cin.tie(NULL);}
#define nln cout << '\n'
#define ll long long int
#define INF (ll)1e+12
#define MAX 300100
#define mp(i, j) make_pair(i, j)
#define here cout  << "here";nln;
#define mul(a, b, mod) (((a % mod) * (b % mod)) % mod)
#define add(a, b, mod) (((a % mod) + (b % mod)) % mod)
#define inf 100000
#define M 1000000000LL

using namespace std;

ll a[200100];

int main()
{
    ll n, l, k, i, ans, cnt, x;

    cin >> n;
    for(i = 1; i <= n; i++){
        cin >> x;
        a[x] = i;
    }

    cnt = 1;
    ans = n;
    for(i = 2; i <= n ; i++){
        if(a[i] < a[i-1]){
           ans = min(n-cnt, ans);
           cnt = 0;
        }
        cnt++;
    }

    ans = min(n-cnt, ans);

    cout << ans << endl;
}


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

int main() {
    int N;
    cin >> N;
    int A[N];
    vector<vector<int>> X(N), Y(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        for (int j = 0; j < A[i]; j++) {
            int x, y;
            cin >> x >> y;
            X[i].push_back(x);
            Y[i].push_back(y);
        }
    }

    // 全部のケースをさらう=>bit全探索

    // 正直者設定された人の証言がそのケースに合致しているか記録する

    // 合致していればok，正直者の人数MAXを更新していく

    int MAX = 0;
    for (int i = 0; i < (1 << N); i++) {
        bool ok = true;
        int count = 0;
        for (int j = 0; j < N; j++) {
            if (i & (1 << j)) count ++; // 1なら正直者
        }

        for (int j = 0; j < N; j++) {
            if (i & (1 << j)) {
                for (int k = 0; k < A[j]; k++) {
                    if (Y[j][k] == 1 && !(i & (1 << X[j][k]-1))) ok = false; 
                    if (Y[j][k] == 0 && (i & (1 << X[j][k]-1))) ok = false;
                }
            }
        }

        if (ok) MAX = max(MAX, count);
    }

    cout << MAX << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdint>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <cassert>
#include <climits>
#include <string>
#include <bitset>
#include <cfloat>
#include <unordered_set>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<pair<int, int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<ll> > vvll;

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, n) for (int i = 1; i <= (n); ++i)
#define irep(it, stl) for (auto it = stl.begin(); it != stl.end(); it++)
#define drep(i, n) for (int i = (n)-1; i >= 0; --i)
#define mes(a) cout << (a) << endl
#define dmes(a, b) cout << (a) << " " << (b) << endl
#define re0 return 0
#define mp(p, q) make_pair(p, q)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define Sort(a) sort(a.begin(), a.end())
#define rSort(a) sort(a.rbegin(), a.rend())
#define MATHPI acos(-1)
#define itn int;
int dx[8] = { 1, 0, -1, 0, 1, -1, -1, 1 };
int dy[8] = { 0, 1, 0, -1, 1, 1, -1, -1 };
template <class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template <class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
struct io { io() { ios::sync_with_stdio(false); cin.tie(0); } };
const int INF = INT_MAX;
const ll LLINF = 1LL << 60;
const ll MOD = 1000000007;
const double EPS = 1e-9;

signed main(void)
{    
    ll n, m, k;
    cin >> n >> m >> k;
    
    ll r = 0;
    
    vll as(n+1), bs(m+1);
    as[0] = 0; bs[0] = 0;
    
    
    ll a, b;
    ll amax = 0;
    ll bmax = 0;
    rrep(i, n) {
        cin >> a;
        as[i] = as[i-1] + a;
        if (as[i] <= k) amax++;
    }
    rrep(i, m) {
        cin >> b;
        bs[i] = bs[i-1] + b;
        if (bs[i] <= k) bmax++;
    }
    
    for(ll i = 0; i <= amax; i++) {
        if (as[i] > k) continue;
        for(ll j = bmax; j >= 0; j--) {   
            if (as[i] + bs[j] <= k) {
                r = max(r, i+j);
                bmax = j;
                break;
            }
            
        }
        
    }
    
    mes(r);
    
    
    
    
    
    
}

Measured memory_bytes: 6408
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <cassert>

using namespace std; using ll=long long; const int INF=1e9;
typedef pair<int,int> P;

int main() {
  int n,k; cin>>n>>k;
  bool su[n]={};
  for(int i=0;i<k;i++) {
    int d; cin>>d;
    for(int j=0;j<d;j++) {
      int a; cin>>a; a--;
      su[a]=true;
    }
  }
  int an = 0;
  for(int i=0;i<n;i++) {
    an += su[i]==false;
  }
  cout<<an<<endl;
}

Measured memory_bytes: 3632
n,m=map(int,input().split())
if n%2==0:
  counter=0
  for i in range(min(m,n//4)):
    print(i+1)
    print(n-i)
    counter+=1
  if counter<m:
    for i in range(n//4,m):
      print(i+1)
      print(n-i-1)
else:
  for i in range(m):
    print(i+1)
    print(n-i)

Measured memory_bytes: 9264
#include <iostream>
using namespace std;
int dp[10005];
int main(){
      int n,sum,vs[1005],ws[1005];cin >> n >> sum;
      for (int i = 0;i<n;i++)cin >> vs[i] >> ws[i];
      for (int i = 0;i <= sum;i++)for(int j = 0;j <n;j++)if(i + ws[j] <=sum ) dp[i + ws[j]] = max(dp[i]+vs[j],dp[i+ws[j]]);
      cout << dp[sum] << endl;
}

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

#define rep(i,n) for(long long int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(long long int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(long long int i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define pb(q) push_back(q)
#define Size(n) (n).size()
#define Cout(x) cout<<(x)<<endl

typedef long long ll;

using namespace std;

const int INF = 1e9,MOD = 1e9 + 7,ohara = 1e6;
const ll LINF = 1e18;
long long int n,cnt=0,ans=0,a,b,c,d,cmp,cmpp,m,h[ohara],w,x[ohara],y[ohara],sum=0,pos;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
string alph("abcdefghijklmnopqrstuvwxyz"),s;
bool fl;
struct edge{int to,cost;};

//-------------------------↓↓↓↓↓↓------------------------

int main(void){
  
       cin.tie(0);
    ios::sync_with_stdio(false);
      
      cin>>n;
      rep(i,n)cin>>x[i]>>y[i]>>h[i];
      rep(Cx,101){
        rep(Cy,101){
          map<ll,ll> mp;
          ll data[n+1];
          cnt=0;
          ll ma=0;
          rep(i,n){
            if(h[i]!=0){
              pos=abs(x[i]-Cx)+abs(y[i]-Cy);
              mp[pos+h[i]]++;
              data[cnt++]=pos+h[i];
              ma=max(ma,pos+h[i]);
            }
            else{
              pos=abs(x[i]-Cx)+abs(y[i]-Cy);
              ma=max(ma,pos);
              rep(j,pos+1)mp[j]++;
            }
          }
          rep(i,cnt){
            if(mp[data[i]]==n){
              cout<<Cx<<" "<<Cy<<" "<<data[i]<<"\n";
              return 0;
            }
          }
        }
      }
    
       
return 0;
}


Measured memory_bytes: 4352
#include <iostream>
#include <algorithm>
#include <cmath>
#include <limits>
#include <vector>
#include <cstdio>
#include <bits/stdc++.h>
#include <set>
#include <map>
#include <stdio.h>
#include <stack>
#include <queue>
#include <deque>
#include <numeric>
#include <bits/stdc++.h>
#include <utility>
#include <iomanip>

#define ALL(obj) (obj).begin(), (obj).end()
#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define RFOR(i,a,b) for(int i = (a); (b) <= i; i--)
#define REP(i,n) for(int i = 0; i < (n); i++)
#define RREP(i,n) for(int i = n; n <= i; i--)
#define ABS(a) ((a < 0) ? ((-1)*(a)) : (a))
#define elif else if
#define MOD 1000000007
#define INF (1<<29)

using namespace std;

#define ld long double
#define ll long long

map <int ,int> mpa,mpb;
typedef pair<ll, ll> P;
priority_queue<P, vector<P>, greater<P>> pque;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  double N,A,B;
  cin >> N >> A >> B;
  vector<double> v;
  ll h;
  for(int i=0;i<N;i++){
    cin >> h;
    v.push_back(h);
  }
  ll ans=0;
  ll cnt=0;
  sort(v.begin(),v.end());
  ll lb=0,ub=1000000000;
  while(ub-lb>1){
    cnt=0;
    ll mid=(lb+ub)/2;
    for(int i=0;i<N;i++){
      if(v[i]<=B*mid)continue;
      else if(v[i]>B*mid){
        cnt+=ceil((v[i]-B*mid)/(A-B));
      }
    }
    if(cnt<=mid){
      ub=mid;
    }else{
      lb=mid;
    }
  }
  cout << lb+1 << endl;
  return 0;
}

Measured memory_bytes: 1400
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)

#A
def A():
    n = I()
    if n <= 1000000000:
        print(0,0,1,0,0,n)
    else:
        b = 1000000000
        a = 1
        y = -n%1000000000
        x = (n+a*y)//b
        print(0,0,x,y,a,b)
        return

    return

#B
def B():
    n,k = LI()
    a = LI()
    s = []
    f = [1]*1000000
    for i in range(k):
        for j in range(n):
            aj = a[j]
            if f[aj]:
                s.append(aj)
                f[aj] = 0
            else:
                while 1:
                    x = s.pop(-1)
                    f[x] = 1
                    if x == aj:
                        break
        print(i+1,s)
    return

#C
mod = 998244353
def C():
    def comb(a,b):
        if a < b:
            return 1
        return fact[a]*inv[b]*inv[a-b]%mod
    n,m = LI()
    MA = 3*m+max(n,2*m)-1
    fact = [1]*(MA+1)
    for i in range(MA):
        fact[i+1] = fact[i]*(i+1)%mod
    inv = [1]*(MA+1)
    inv[MA] = pow(fact[MA],mod-2,mod)
    for i in range(MA)[::-1]:
        inv[i] = inv[i+1]*(i+1)%mod
    ans = 0
    for k in range(min(m,n)+1):
        if (3*m-k)%2 == 0:
            ans += comb(n,k)*comb((3*m-k)//2+n-1,n-1) #奇数の数がk個かつ総和が3mとなるパターンの総数(n個のうちk個に1を割り振る→総和が3m-kとなるパターンの総数を求める)
            ans %= mod
    ans -= n*comb(3*m-(2*m+1)+n-1,n-1)
    ans %= mod
    print(ans)

    return

#D
def D():
    return

#E
def E():
    n = I()

    return

#F
def F():
    n = I()

    return

#Solve
if __name__ == "__main__":
    C()


Measured memory_bytes: 80492
import sys
from collections import deque
input = lambda: sys.stdin.readline().rstrip()
tdlist = lambda i, j, value=0: [[value] * j for _ in range(i)]

n = int(input())
m = n * (n-1) // 2
graph = [list() for _ in range(m)]
deg = [0] * m

to_id = tdlist(n, n)
cnt = 0
for i in range(n):
    for j in range(i+1, n):
        to_id[i][j], to_id[j][i] = cnt, cnt
        cnt += 1

for i in range(n):
    a = list(map(int, input().split()))
    for j in range(n-2):
        v = to_id[i][a[j]-1]
        u = to_id[i][a[j+1]-1]
        graph[v].append(u)
        deg[u] += 1

q = deque(v for v in range(m) if deg[v] == 0)
cnt = 0
dp = [0] * m

while q:
    v = q.popleft()
    cnt += 1
    for u in graph[v]:
        deg[u] -= 1
        dp[u] = max(dp[u], dp[v] + 1)
        if deg[u] == 0:
            q.append(u)

print(-1 if cnt != m else max(dp)+1)


Measured memory_bytes: 123220
while True:
 H,W = list(map(int, input().split() ))
 if H==0 and W==0:
  break
 for r in range(H):
  for c in range(W):
   if (r+c)%2 == 0:
    print("#",end="")
   else:
    print(".",end="")
  print()
 print()




Measured memory_bytes: 7004
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 100

typedef pair<int,int> P;


struct Edge{
	Edge(int arg_to,int arg_capacity,int arg_cost,int arg_rev_index){
		to = arg_to;
		capacity = arg_capacity;
		cost = arg_cost;
		rev_index = arg_rev_index;
	}

	int to,capacity,cost,rev_index;
};

int V;
vector<Edge> G[NUM];
int h[NUM];
int dist[NUM];
int pre_node[NUM],pre_edge[NUM];

void add_edge(int from,int to,int capacity,int cost){
	G[from].push_back(Edge(to,capacity,cost,G[to].size()));
	G[to].push_back(Edge(from,0,-cost,G[from].size()-1));
}

int min_cost_flow(int source,int sink,int flow){
	int ret = 0;
	for(int i = 0; i < V; i++)h[i] = 0;
	while(flow > 0){
		priority_queue<P,vector<P>,greater<P> > Q;
		for(int i = 0; i < V; i++)dist[i] = BIG_NUM;
		dist[source] = 0;
		Q.push(P(0,source));

		while(!Q.empty()){
			P p = Q.top();
			Q.pop();
			int node_id = p.second;
			if(dist[node_id] < p.first)continue;
			for(int i = 0; i < G[node_id].size(); i++){
				Edge &e = G[node_id][i];
				if(e.capacity > 0 && dist[e.to] > dist[node_id]+e.cost+h[node_id]-h[e.to]){
					dist[e.to] = dist[node_id]+e.cost+h[node_id]-h[e.to];
					pre_node[e.to] = node_id;
					pre_edge[e.to] = i;
					Q.push(P(dist[e.to],e.to));
				}
			}
		}

		if(dist[sink] == BIG_NUM){
			return -1;
		}

		for(int node_id = 0; node_id < V; node_id++)h[node_id] += dist[node_id];

		int tmp_flow = flow;
		for(int node_id = sink; node_id != source; node_id = pre_node[node_id]){
			tmp_flow = min(tmp_flow,G[pre_node[node_id]][pre_edge[node_id]].capacity);
		}
		flow -= tmp_flow;
		ret += tmp_flow*h[sink];
		for(int node_id = sink; node_id != source; node_id = pre_node[node_id]){
			Edge &e = G[pre_node[node_id]][pre_edge[node_id]];
			e.capacity -= tmp_flow;
			G[node_id][e.rev_index].capacity += tmp_flow;
		}
	}
	return ret;
}

int main(){

	int E,F;
	scanf("%d %d %d",&V,&E,&F);

	int from,to,capacity,cost;
	for(int loop = 0; loop < E; loop++){
		scanf("%d %d %d %d",&from,&to,&capacity,&cost);
		add_edge(from,to,capacity,cost);
	}

	printf("%d\n", min_cost_flow(0,V-1,F));

	return 0;
}



Measured memory_bytes: 3280
import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int a[] = new int[5];
        int b[] = new int[5];
        int c[] = new int[5];
        int min = 0;
        int minsize = 9;
        int sum = 0;

        for (int i = 0; i < 5; i++) {
            a[i] = scan.nextInt();
            b[i] = a[i] % 10;
            c[i] = a[i] / 10;
            if((b[i] <= minsize) && (b[i] != 0)){
                min = i;
                minsize = b[i];
            }
        }

        for(int x = 0; x < min ; x++){

            if(b[x] != 0 ){
                c[x] = c[x] + 1;
            }
            sum = c[x]*10 + sum;
        }

        for(int y = (min + 1) ; y < 5 ; y++){

            if(b[y] != 0 ){
                c[y] = c[y] + 1;
            }
            sum = c[y]*10 + sum;
        }

        sum = sum + c[min]*10 + b[min];
        System.out.println(sum);

    }
}

Measured memory_bytes: 23508
#include <iostream>
#include <algorithm>
#include<string>
#include<cmath>
#include<stack>
#include <vector>
#include<queue>
#include <random>
using namespace std;



int main() {
	int n, a[114514],num=1,ans=0;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	sort(a, a + n);
	for (int i = 0; i < n-1; i++) {
		if (a[i+1] == a[i]) {
			num++;
		}
		else {
			if (num > a[i]) {
				ans += num - a[i];
			}
			else if(num<a[i]) {
				ans += num;
			}
			num = 1;
		}
	}
	if (num != a[n - 1]) {
		if (num < a[n - 1]) {
			ans += num;
		}
		else {
			ans += num - a[n - 1];
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 640
using System;
using System.Linq;
namespace Sample
{
  class Sample
  {
    static void Main(string[] args)
    {string[] str=Console.ReadLine().Split(' ');
     int X=int.Parse(str[0]);
     int Y=int.Parse(str[1]);
     if(Y>X){
       Console.WriteLine(0);
     }else{
       Console.WriteLine(X-Y);
     }
    }
    
  }

}


Measured memory_bytes: 27268
#include <iostream>
#include <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
using namespace std;
#define REP(i, j) for(int i = 0; i < (int)(j); ++i)
#define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i)
#define SORT(v) sort((v).begin(), (v).end())
#define REVERSE(v) reverse((v).begin(), (v).end())
typedef pair<int, vector<int> > P;
const int L = 30;

void rotate(int type, vector<int> &v){
  if(type == 0){
    swap(v[0], v[23]);
    swap(v[3], v[26]);
    swap(v[6], v[29]);
    swap(v[9], v[20]);
    swap(v[15], v[17]);
  } else if(type == 1){
    swap(v[2], v[21]);
    swap(v[5], v[24]);
    swap(v[8], v[27]);
    swap(v[11], v[18]);
    swap(v[12], v[14]);
  } else if(type == 2){
    swap(v[0], v[27]);
    swap(v[1], v[28]);
    swap(v[2], v[29]);
    swap(v[14], v[15]);
    swap(v[18], v[20]);
  } else if(type == 3){
    swap(v[6], v[21]);
    swap(v[7], v[22]);
    swap(v[8], v[23]);
    swap(v[12], v[17]);
    swap(v[9], v[11]);
  }
}

bool isEnd(vector<int> &v){
  vector<int> list[6] = {
    {0, 1, 2, 3, 4, 5, 6, 7, 8},
    {21, 22, 23, 24, 25, 26, 27, 28, 29},
    {9, 10, 11},
    {12, 13, 14},
    {15, 16, 17},
    {18, 19, 20}
  };
  REP(i, 6) REP(j, list[i].size()) if(v[list[i][j]] != v[list[i][0]]) return false;
  return true;
}

int bfs(vector<int> &v){
  queue<P> open;
  open.push(P(0, v));
  set< vector<int> > closed;
  closed.insert(v);
  while(!open.empty()){
    P now = open.front(); open.pop();
    if(isEnd(now.second)) return now.first;
    REP(i, 4){
      rotate(i, now.second);
      if(closed.find(now.second) == closed.end()){
        open.push(P(now.first + 1, now.second));
        closed.insert(now.second);
      }
      rotate(i, now.second);
    }
  }
  return 8;
}
 
int main() {
  int N; cin >>N;
  vector<int> v(L);
  while(N--){
    REP(i, L) cin >>v[i];
    cout <<bfs(v) <<endl;
  }
  return 0;
}

Measured memory_bytes: 3212
import numpy as np
import itertools

N ,M ,Q = map(int,input().split(' '))
ABCD = []
for _ in range(Q):
    ABCD.append(list(map(int,input().split())))

ALL = list(itertools.combinations_with_replacement(range(1,M+1), N))
MAX = 0
for row in ALL:
    SUM = 0
    for a,b,c,d in ABCD:
        if (row[b-1] - row[a-1]) == c:
            SUM += d

    MAX = max(MAX,SUM)
print(MAX)

Measured memory_bytes: 39552
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <iomanip>
#include <stack>
#include <queue>
#include <numeric>
#include <map>
#include <unordered_map>
#include <set>
#include <fstream>
#include <chrono>
#include <random>
#include <bitset>
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) ((int)(x).size())
#define pb push_back
#define mod 1000000007
using ll = long long;
using namespace std;

int main(){
  int N; cin >> N;
  string S;
  cin >> S;
  int ans = 0;
  rep(i,sz(S)){
    if(S.substr(i,3) == "ABC") ans++;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
i=[ 1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]

K= int(input())
print(i[K-1])


Measured memory_bytes: 2940
#include<stdio.h>
#include<stdlib.h>

struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;
#define NIL NULL

Node root;

Node treeMinimum(Node x){
  while( x->left != NIL ) x = x->left;
  return x;
}
Node treeMaximum(Node x){
  while( x->right != NIL ) x = x->right;
  return x;
}

Node treeSearch(Node u, int k){
  while( u != NIL && k != u->key ){
    if ( k < u->key ) u = u->left;
    else u = u->right;
  }
  return u;
}

Node treeSuccessor(Node x){
  if ( x->right != NIL ) return treeMinimum(x->right);
  Node y = x->parent;
  while( y != NIL && x == y->right ){
    x = y;
    y = y->parent;
  }
  return y;
}

void treeDelete(Node z){
  Node y; // node to be deleted
  Node x; // child of y

  if ( z->left == NIL || z->right == NIL ) y = z;
  else y = treeSuccessor(z);
  if ( y->left != NIL ) x = y->left;
  else x = y->right;

  if ( x != NIL ) x->parent = y->parent;

  if ( y->parent == NIL ){
    root = x;
  } else {
    if (y == y->parent->left) y->parent->left = x;
    else y->parent->right = x;
  }

  if ( y != z ){
    z->key = y->key;
  }

  free(y);
}

void insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;

  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;

  while( x != NIL ){
    y = x;
    if ( z->key < x->key ){
      x = x->left;
    } else {
      x = x->right;
    }
  }

  z->parent = y;
  if ( y == NIL ){
    root = z;
  } else {
    if (z->key < y->key) {
      y->left = z;
    } else {
      y->right = z;
    }
  }
}

void inorder(Node u){
  if ( u == NIL ) return;
  inorder(u->left);
  printf(" %d", u->key);
  inorder(u->right);
}
void preorder(Node u){
  if ( u == NIL ) return;
  printf(" %d", u->key);
  preorder(u->left);
  preorder(u->right);
}


int main(){
  int n, i, x;
  char com[10];
  scanf("%d", &n);
  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( strcmp(com, "find") == 0 ){
      scanf("%d", &x);
      Node t = treeSearch(root, x);
	if ( t != NIL ) printf("yes\n");
	else printf("no\n");
      }
    else if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    }
    else if ( strcmp(com, "print") == 0 ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }
    else if ( strcmp(com, "delete") == 0 ){
      scanf("%d", &x);
      treeDelete(treeSearch(root, x));
    }
  }

  return 0;
}

Measured memory_bytes: 19364
# -*- coding: utf-8 -*-
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

S = readline().decode().rstrip()
N = len(S)
x,y = map(int,readline().split())
t_cnt = 0
cnt_x1 = 0
cnt_x2 = 0
cnt_y = 0
X = []
Y = []
for i in range(N):
    if S[i] == 'F':
        if t_cnt == 0:
            cnt_x1 += 1
        else:
            if t_cnt % 2 == 0:
                cnt_x2 += 1
            else:
                cnt_y += 1
    else:
        t_cnt += 1
        if cnt_x2 != 0:
            X.append(cnt_x2)
            cnt_x2 = 0
        if cnt_y != 0:
            Y.append(cnt_y)
            cnt_y = 0
            
if cnt_x2 != 0:
    X.append(cnt_x2)
    cnt_x2 = 0
if cnt_y != 0:
    Y.append(cnt_y)
    cnt_y = 0

xN = len(X)
yN = len(Y)    
sumX = sum(X)
sumY = sum(Y)
x -= cnt_x1

if sumX - x < 0 or (sumX - x) % 2 != 0:
    print('No')
    sys.exit()
else:  
    xx = (sumX - x) // 2
if sumY - y < 0 or (sumY - y) % 2 != 0:
    print('No')
    sys.exit()
else:  
    yy = (sumY - y) // 2
    
dp_x = [0]*(xx+1) 
dp_x[0] = 1
for i in range(xN):
    w = X[i]
    for j in range(xx,w-1,-1):
        dp_x[j] = dp_x[j] or dp_x[j-w]
        
dp_y = [0]*(yy+1) 
dp_y[0] = 1
for i in range(yN):
    w = Y[i]
    for j in range(yy,w-1,-1):
        dp_y[j] = dp_y[j] or dp_y[j-w]

if dp_x[xx] and dp_y[yy]:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 74096
#include <iostream>
#include <fstream>
#include <string>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <utility>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <unordered_map>
#define MOD 1000000007
#define int long long
using namespace std;
using P = pair<int, int>;
using ll = long long;
using prique = priority_queue<int>;

signed main(){
    string s;
    cin>>s;
    vector<int> c[s.size()];
    for(int i=s.size()-1;i>=0;i--){
        if(s.size()-i>=5&&s.substr(i,5)=="dream"){
            c[i].push_back(5);
            if(i+5<s.size()){
                int m=0;
                for(int j=0;j<c[i+5].size();j++){
                    m=max(m,c[i+5][j]);
                }
                c[i][c[i].size()-1]+=m;
            }
        }
        if(s.size()-i>=5&&s.substr(i,5)=="erase"){
            c[i].push_back(5);
            if(i+5<s.size()){
                int m=0;
                for(int j=0;j<c[i+5].size();j++){
                    m=max(m,c[i+5][j]);
                }
                c[i][c[i].size()-1]+=m;
            }
        }
        if(s.size()-i>=6&&s.substr(i,6)=="eraser"){
            c[i].push_back(6);
            if(i+6<s.size()){
                int m=0;
                for(int j=0;j<c[i+6].size();j++){
                    m=max(m,c[i+6][j]);
                }
                c[i][c[i].size()-1]+=m;
            }
        }
        if(s.size()-i>=7&&s.substr(i,7)=="dreamer"){
            c[i].push_back(7);
            if(i+7<s.size()){
                int m=0;
                for(int j=0;j<c[i+7].size();j++){
                    m=max(m,c[i+7][j]);
                }
                c[i][c[i].size()-1]+=m;
            }
        }
    }
    bool ans=false;
    for(int i=0;i<c[0].size();i++){
        if(c[0][i]==s.size())ans=true;
    }
    if(ans)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    return 0;
}





Measured memory_bytes: 3200
#include <cstdio>
#include <iostream>
#include <sstream>
#include <vector>

using namespace std;

int main() {
    int n;
    char c;
    string str, newstr;
    string::iterator it;

    while (cin >> n) {
        if(n == 0) break;

        str.clear();
        newstr.clear();

        c = getchar();
        while (c = getchar()) {
            if(c == '\n') break;
            str.push_back(c);
        }

        for (int i=0; i<n; i++) {
            char num = 'a';
            int cont;
            ostringstream s;

            newstr.clear();
            it = str.begin();
            while (it != str.end()) {
                if(*it != num) {
                    if(it != str.begin()) {
                        s << cont << num;
                    }
                    cont = 1;
                    num = *it;
                } else {
                    cont++;
                }
                it++;
            }
            s << cont << num;
            newstr += s.str();

            str = newstr;
        }

        it = str.begin();
        while (it != str.end()) {
            cout << *it;
            it++;
        }
        cout << endl;
    }

    return 0;
}

Measured memory_bytes: 3236
/*** author: yuji9511 ***/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using lpair = pair<ll, ll>;
const ll MOD = 998244353;
const ll INF = 1e18;
#define rep(i,m,n) for(ll i=(m);i<(n);i++)
#define rrep(i,m,n) for(ll i=(m);i>=(n);i--)
#define printa(x,n) for(ll i=0;i<n;i++){cout<<(x[i])<<" \n"[i==n-1];};
void print() {}
template <class H,class... T>
void print(H&& h, T&&... t){cout<<h<<" \n"[sizeof...(t)==0];print(forward<T>(t)...);}
ll dp[2][90010] = {};
ll dp2[2][90010] = {};
ll power(ll x, ll n){
    if(n == 0) return 1LL;
    ll res = power(x * x % MOD, n/2);
    if(n % 2 == 1) res = res * x % MOD;
    return res;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N;
    cin >> N;
    ll a[310];
    rep(i,0,N) cin >> a[i];
    dp[0][0] = 1;
    ll sum = 0;
    rep(i,0,N) sum += a[i];
    ll cur = 0, nxt = 1;
    rep(i,0,N){
        rep(j,0,300 * N + 1){
            dp[nxt][j] = 0;
            if(j - a[i] >= 0) dp[nxt][j] += dp[cur][j - a[i]];
            (dp[nxt][j] += 2 * dp[cur][j]) %= MOD;
        }
        cur ^= 1;
        nxt ^= 1;
    }

    dp2[0][0] = 1;
    cur = 0, nxt = 1;
    rep(i,0,N){
        rep(j,0,300*N+1){
            dp2[nxt][j] = 0;
            if(j - a[i] >= 0) dp2[nxt][j] += dp2[cur][j - a[i]];
            (dp2[nxt][j] += dp2[cur][j]) %= MOD;
        }
        cur ^= 1;
        nxt ^= 1;
    }

    ll ans = 0;
    rep(i,(sum+1)/2, sum+1){
        (ans += dp[cur][i]) %= MOD;
    }
    if(sum % 2 == 0){
        ans -= dp2[cur][sum/2];
        ans = (ans + MOD) % MOD;
    }
    ans *= 3;
    ans %= MOD;

    ans = (power(3,N) - ans + MOD) % MOD;
    print(ans);

}

Measured memory_bytes: 3072
#include <stdio.h>

int main(void)
{
	int a, b, c;
	int i, ans = 0;
	
	scanf("%d %d %d", &a, &b, &c);


	for (i = 0; i <= b - a; i++) {
		if (c % (a + i) == 0) {
			ans++;
		}
		//printf("*");
	}

	printf("%d\n", ans);

		
	
	return 0;
}


Measured memory_bytes: 2056
S = input()
K = int(input())
N = len(S)

dp = [[[0 for _ in range(2)] for _ in range(4)] for _ in range(105)]
dp[0][0][0] = 1

for i in range(N):
    for j in range(4):
        for k in range(2):
            nd = int(S[i])
            for d in range(10):
                ni = i+1
                nj = j
                nk = k
                if d != 0:
                    nj += 1
                if nj > K:
                    continue
                if k == 0:
                    if d > nd:
                        continue
                    if d < nd:
                        nk = 1
                dp[ni][nj][nk] += dp[i][j][k]

print(dp[N][K][0] + dp[N][K][1])


Measured memory_bytes: 41200
#include<bits/stdc++.h>
using namespace std;
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define pa pair<int,int>
#define mod 1000000007
#define ll long long
#define mk make_pair
#define pb push_back
#define fi first
#define se second
#define cl(x) memset(x,0,sizeof x)
#ifdef Devil_Gary
#define bug(x) cout<<(#x)<<" "<<(x)<<endl
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define bug(x)
#define debug(...)
#endif
const int INF = 0x7fffffff;
const int N=3e5+5;
/*
char *TT,*mo,but[(1<<15)+2];
#define getchar() ((TT==mo&&(mo=(TT=but)+fread(but,1,1<<15,stdin),TT==mo))?-1:*TT++)//*/
inline int read(){
    int x=0,rev=0,ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')rev=1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return rev?-x:x;
}
int n,a[N],b[N],ans=INT_MAX;
char s[N];
int main(){
#ifdef Devil_Gary
	freopen("in.txt","r",stdin);
#endif
	n=read();
	scanf("%s",s+1);
	for(int i=1;i<=n;i++) a[i]=(s[i]=='E');
	for(int i=1,t=0;i<=n;i++) {
		b[i]+=t;
		t+=(!a[i]);
	}
	for(int i=n,t=0;i;--i) {
		b[i]+=t;
		t+=(a[i]);
	}
	for(int i=1;i<=n;i++) ans=min(ans,b[i]); 
	cout<<ans<<endl;
}



Measured memory_bytes: 2944
n,m,q=map(int,input().split())
x=[[0]*(n+1) for i in range(n+1)]
c=[[0]*(n+1) for i in range(n+1)]
for i in range(m):
  l,r=map(int,input().split())
  x[l][r]+=1
for i in range(1,n+1):
  for j in range(1,n+1):
    c[i][j]=c[i][j-1]+x[i][j]
for i in range(q):
  p,q=map(int,input().split())
  s=0
  for j in range(p,q+1):
    s+=c[j][q]-c[j][p-1]
  print(s)

Measured memory_bytes: 55384
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(v) v.begin(), v.end()
typedef long long ll;

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; }

#include <bits/stdc++.h>
using namespace std;

static const double pi = 3.141592653589793;

int main(){
  double d,a,x=0.0,y=0.0,z=90.0;
  char c;
  while(cin>>d>>c>>a){
      x+=d*cos(z*pi/180);
      y+=d*sin(z*pi/180);
      z-=a;
  }
  
  cout<<(int)x<<endl;
  cout<<(int)y<<endl;
    
  return 0;
}


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

// cumsum : いままでの左側の和
ll dfs(string s, int pos, ll cumsum) {
    if (s.length() == pos) return stoll(s) + cumsum;
    // 分割するパターン
    ll div = dfs(s.substr(pos), 1, cumsum + stoll(s.substr(0, pos)));
    // 分割しないパターン
    ll nondiv = dfs(s, pos+1, cumsum);
    
    return div + nondiv;
}

int main() {
    string S;
    cin >> S;
    ll ans = dfs(S, 1, 0);
    cout << ans << endl;
}

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

int main()
{
  int x, y;
  cin >> x >> y;
  if (y % 2 != 0 || y > x * 4 || y < x * 2)
  {
    cout << "No" << endl;
    return 0;
  }
  cout << "Yes" << endl;
}


Measured memory_bytes: 3640
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

import java.util.StringTokenizer;

public class Main {
	private static final int MOD = (int)Math.pow(10, 9);
	public static void main(String[] args) {
		FastReader sc = new FastReader();
		int n = sc.nextInt();
		int k = sc.nextInt();
		int res = 0;
		
		for (int i = 0; i < n; i++) {
			int height = sc.nextInt();
			if (height >= k) { res++; }
		}
		
		System.out.println(res);
	}
	
	static class FastReader {
	    BufferedReader br;
	    StringTokenizer st;
	
	    public FastReader() {
	      br = new BufferedReader(new InputStreamReader(System.in));
	    }
	  
	    String next() { 
	      while (st == null || !st.hasMoreElements()) {
	        try {
	          st = new StringTokenizer(br.readLine());
	        } catch (IOException  e) {
	          e.printStackTrace();
	        }
	      }
	      return st.nextToken();
	    }
	
	    int nextInt() {
	      return Integer.parseInt(next());
	    }
	
	    long nextLong() {
	      return Long.parseLong(next());
	    }
	
	    double nextDouble() { 
	      return Double.parseDouble(next());
	    }
	
	    String nextLine() {
	      String str = "";
	        try{
	            str = br.readLine();
	        } catch (IOException e) {
	            e.printStackTrace();
	        }
	        return str;
	      }
	  }
}


Measured memory_bytes: 33380
n = int(input())
def is_prime(num):
    import math
    if num == 2:
        return True
    elif num <  3 or num % 2 == 0:
        return False
    for i in range(3, int(math.sqrt(num)) + 1, 2):
        if num % i == 0:
            return False
    return True

if is_prime(n):
    print(n-1)
    exit()

ans = float('inf')
for i in range(int(n**0.5), 0, -1):
    if n%i == 0:
        ans = min(ans, (i-1)+(n//i-1))
print(ans)

Measured memory_bytes: 3064
x, y = map(int, input().split())
if x <= y:
    if x == 0:
        print(y)
    elif y == 0:
        print(- x)
    elif x * y > 0:
        print(y - x)
    else:
        if abs(x) <= abs(y) :
            print(y - abs(x) + 1)
        else :
            print(abs(x) - abs(y) + 1)
else:
    if x == 0:
        print(abs(y) + 1)
    elif y == 0:
        print(abs(x) + 1)
    elif x * y > 0:
        print(x - y + 2)
    else:
        if abs(x) > abs(y):
            print(abs(x) - abs(y) + 1)
        else:
            print(abs(y) - abs(x) + 1)

Measured memory_bytes: 3064
parseInt(x) = parse(Int, x)
parseMap(x::Array{SubString{String},1}) = map(parseInt, x)

function main()
	n,m = readline() |> split |> parseMap
	d = zeros(Int,n)
	for i in 1:m
		a,b = readline() |> split |> parseMap
		d[a] += 1
		d[b] += 1
	end
	f = 0
	for i in 1:n
		if d[i]%2==1
			f = 1
			break
		end
	end
	println(f==0?"YES":"NO")
end

main()

Measured memory_bytes: 155812
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

const int MOD = 1000000007;

int solveWithMod(int N, int M, vector<int> a, int mod) {
    vector<bool> flg(N + 1, true);
    vector<int> steps(N + 1, 0); steps[0] = 1; //ここでsteps[i]はi段目にいる場合の数である。

    if(M > 0) {
        for(int i = 0; i < M; i++) flg[a[i]] = false;
    }

    for(int i = 0; i <= N - 1; i++) {
        for(int j = i + 1; j <= N && j <= i + 2; j++) {
            if(!flg[j]) continue;
            steps[j] += steps[i];
            steps[j] %= mod;
        }
    }

    int ans = steps[N];

    return ans;
}

int main() {
    int N, M;
    vector<int> a;
     cin >> N >> M;
  if(M > 0) {
     for(int i = 0; i < M; i++) {
         int ai;
         cin >> ai;
         a.push_back(ai);
     }
  }
    cout << solveWithMod(N, M, a, MOD) << endl;
    return 0;
}

Measured memory_bytes: 1528
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main(){
  int n,k;
  cin >> n>>k;
  vector<int> ni(21);
  ni.at(0)=1;
  int x=1;
  for(int i=1;i<21;i++){
    x=x*2;
    ni.at(i)=x;
  }
  double ans=0;
  for(int i=1;i<=n;i++){
    double p=(double)k/i;
    double ke=1;
    if(i>=k){
      ans++;
      continue;
    }
    for(int j=0;j<21;j++){
      if(ni.at(j)>=p){
        ans+=ke;
        break;
      }
      ke/=2;
    }
  }
  ans/=n;
  printf("%.10lf\n",ans);
}
 

Measured memory_bytes: 3780
var line;
var readline = require('readline');
var rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

rl.on('line',function(x){
    line = x;
});

rl.on('close',function(){
    if(Number(line) === 7 || Number(line) === 5 || Number(line) === 3){
        console.log("YES");
    }
    else{
        console.log("NO");
    }
})

Measured memory_bytes: 7756
n=int(input())
a=list(map(int, input().split()))
mod=10**9+7
k=a[n-1]
ans=(a[n-2]*k)%mod
for i in range(n-2, -1 ,-1):
    k+=a[i]
    k%=mod
    if (i):
        ans+=(a[i-1]*k)%mod
        ans%=mod
print(ans)


Measured memory_bytes: 31600