akhauriyash/Code-Regression huggingface dataset:
n,s=map(int,input().split())
a=list(map(int,input().split()))
mod=998244353
dp0=[[0]*(s+1) for i in range(n+1)]
dp1=[[0]*(s+1) for i in range(n+1)]
dp2=[[0]*(s+1) for i in range(n+1)]
dp0[0][0]=1
for i in range(n):
  for j in range(s+1):
    if j>=a[i]:
      dp1[i+1][j]=(dp0[i][j-a[i]]+dp1[i][j-a[i]]+dp0[i][j]+dp1[i][j])%mod
      dp2[i+1][j]=(dp0[i][j-a[i]]+dp1[i][j-a[i]]+dp0[i][j]+dp1[i][j]+dp2[i][j])%mod
    else:
      dp0[i+1][j]=dp0[i][j]%mod
      dp1[i+1][j]=(dp0[i][j]+dp1[i][j])%mod
      dp2[i+1][j]=(dp0[i][j]+dp1[i][j]+dp2[i][j])%mod
print(dp2[n][s])

Measured memory_bytes: 246452
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
#include <functional>
typedef long long ll;
using namespace std;
typedef pair<int, int> P;

class LcaTree {
public:
    int N;
    int logN = 1;
    int root;
    vector<vector<int>> G;
    vector<vector<int>> parent;
    vector<int> depth;

    LcaTree(int _N, int _root){
        N = _N;
        root = _root;
        G.resize(N);
        while((1 << logN) < N) logN++;
        parent.resize(logN, vector<int>(N));
        depth.resize(N);
    }

    void make_edge(int s, int t){
        G[s].push_back(t);
        G[t].push_back(s);
    }

    //parent[0]とdepthの初期化
    void dfs(int n, int par, int d){
        parent[0][n] = par;
        depth[n] = d;
        for(int i = 0; i < (int)G[n].size(); i++){
            int nx = G[n][i];
            if(nx != par) dfs(nx, n, d + 1);
        }
    }

    void init(){
        dfs(root, -1, 0);

        //parentの初期化
        for(int k = 0; k < logN - 1; k++){
            for(int i = 0; i < N; i++){
                if(parent[k][i] < 0) parent[k + 1][i] = -1;
                else parent[k + 1][i] = parent[k][parent[k][i]];
            }
        }
    }

    int lca(int u, int v){
        //uとvが同じ深さになるまでたどる
        if(depth[u] > depth[v]) swap(u, v); //u < v

        for(int k = 0; k < logN; k++){
            if((depth[v] - depth[u]) & (1 << k)){
                v = parent[k][v];
            }
        }

        if(u == v) return u;

        for(int k = logN - 1; k >= 0; k--){
            if(parent[k][u] != parent[k][v]){
                u = parent[k][u];
                v = parent[k][v];
            }
        }

        return parent[0][u];
    }
};

//////////////////////////////////////////////////////////////////////

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

    LcaTree tr = LcaTree(N, 0);

    for(int i = 0; i < N; i++){
        int k;
        cin >> k;
        for(int j = 0; j < k; j++){
            int c;
            cin >> c;
            tr.make_edge(i, c);
            //cout << "make_edge " << i << " " << c << endl;
        }
    }

    tr.init();

    int Q;
    cin >> Q;
    vector<int> ans;
    for(int q = 0; q < Q; q++){
        //cout << q << endl;
        int u, v;
        cin >> u >> v;
        ans.push_back(tr.lca(u, v));
    }

    for(int x : ans){
        cout << x << endl;
    }

    return 0;
}


Measured memory_bytes: 19004
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;

typedef pair <int, int> pii;

struct Treap{
	struct Node{
		int x, size, fix, y;
		long long sum;
		Node *left, *right;
		Node(){}
		Node(int _x, int _y, Node *l = NULL, Node *r = NULL){
			x = _x, y = _y, left = l, right = r, fix = rand(), sum = y, size = 1;
		}
		long long lsum(){return left ? left->sum : 0;}
		long long rsum(){return right ? right->sum : 0;}
		int lsize(){return left ? left->size : 0;}
		int rsize(){return right ? right->size : 0;}
		void pushup(){sum = lsum() + rsum() + y, size = lsize() + rsize() + 1;}
	}*T;
	typedef pair <Node *, Node *> pnn;
	void init(){T = NULL;}
	Node *merge(Node *l, Node *r){
		if (!l || !r) return l ? l : r;
		if (l->fix > r->fix){
			l->right = merge(l->right, r);
			l->pushup();
			return l;
		} else {
			r->left = merge(l, r->left);
			r->pushup();
			return r;
		}
	}
	pnn split(Node *T, int val){
		if (!T) return pnn(NULL, NULL);
		if (val < T->x){
			pnn tmp = split(T->left, val);
			T->left = tmp.se, T->pushup();
			return mp(tmp.fi, T);
		} else {
			pnn tmp = split(T->right, val);
			T->right = tmp.fi, T->pushup();
			return mp(T, tmp.se);
		}
	}
	void Insert(int x, int y){
		pnn t = split(T, x);
		T = merge(t.fi, merge(new Node(x, y), t.se));
	}
	long long Query(int x){
		pnn t = split(T, x - 1);
		long long ans = !t.se ? 0 : 1ll * x * t.se->size - t.se->sum - t.se->size;
		T = merge(t.fi, t.se);
		return ans;
	}
}T;

int a[100010];
long long res[200010];

int main(){
	int n, m; scanf("%d%d", &n, &m);
	T.init();
	for (int i = 0; i < n; i++){
		scanf("%d", &a[i]);
	}
	long long sum = 0;
	vector <pii> v;
	for (int i = 1; i < n; i++){
		sum += a[i] > a[i - 1] ? a[i] - a[i - 1] : a[i] + m - a[i - 1];
		v.push_back(mp(a[i - 1], a[i] < a[i - 1] ? a[i] + m : a[i]));
	}
	sort(v.begin(), v.end());
	int pos = 0;
	long long ans = 0x3f3f3f3f3f3f3f3f;
	for (int i = 1; i <= 2 * m; i++){
		while (pos < v.size() && v[pos].fi < i){
			T.Insert(v[pos].se, v[pos].fi), pos++;
		}
		res[i] = T.Query(i);
	}
	for (int i = 1; i <= m; i++){
		ans = min(ans, sum - res[i] - res[i + m]);
	}
	printf("%lld\n", ans);
	return 0;
}


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

#define rep(i,n) for(int i=0;i<(n);++i)
#define all(x) (x).begin(),(x).end()
#define int long long
using pii = pair<int,int>;
constexpr int INF  = 0x3f3f3f3f;
constexpr int LINF = 0x3f3f3f3f3f3f3f3fLL;

int a[100000050];
signed main(){
    int s;
    cin >> s;
    int cnt = 1;
    while(true){
        cnt++;
        a[s] = 1;
        if(s % 2 == 1){ 
            s = s * 3 + 1;
        }
        else{
            s = s/2;
        }
        if(a[s] == 1){ 
            cout << cnt << '\n';
            break;
        }
    }   
    return 0;
}


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

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef set<int> si;
typedef map<string, int> msi;

#define rep(i, n) \
for(int i = 0; i <n; i++)
#define REP(i, a, b) \
for(int i = int(a); i <= int(b); i++)
#define TRvi(c, it) \
for(vi::iterator it = (c).begin(); it != (c).end(); it++)
#define TRvii(c, it) \
for(vii::iterator it = (c).begin(); it != (c).end(); it++)
#define TRmsi(c, it) \
for(msi::iterator it = (c).begin(); it != (c).end(); it++)

#define INF 2000000000

#define MEMSET_INF 127
#define MEMSET_HALF_INF 63
void solve(){
    int r,c,k;
    cin>>r>>c>>k;
    vector<string> grid(r);
    rep(i,r) cin>>grid[i];
    int ans = 0;
    for(int i=0;i<(1<<r);++i){
        for(int j=0;j<(1<<c);++j){
            int black = 0;
            rep(u,r){
                rep(v,c){
                    if(((i>>u)&1)==0 && ((j>>v)&1)==0 && grid[u][v] =='#'){
                        black+=1;
                    }
                }
            }
            if(black==k){
                ans+=1;
            }
        }
    }
    cout<<ans<<endl;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}


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

int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	string sh; cin >> sh;
	stack <char> ch;
	int z = 0;
	for (int i = 1; i < 4; ++i)
	{
		if (sh[i] != sh[0] && z == 0)
		{
			z = i;
		}
		if (sh[i] != sh[0] && sh[i] != sh[z])
		{
			cout << "No" << endl;
			return 0;
		}
	}
	if (z == 0)
		cout<<"No"<<endl;
	else
		cout << "Yes" << endl;
	return 0;
}

Measured memory_bytes: 3612
fun main(args: Array<String>) {
  val tempature = readLine()!!

  fun countRDay(tempatureDays: String, maxCountDay: Int = 0, counter: Int = 0): Int {
    val newCounter = if(tempatureDays.first() == 'R') counter + 1 else 0
    val maxCount = if(maxCountDay < newCounter) newCounter else maxCountDay
    
    return if(tempatureDays.length == 1) maxCount else countRDay(tempatureDays.substring(1), maxCount, newCounter)
  }
  
  println(countRDay(tempature))
}

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

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, u, v, md = 0;
	cin >> n;
	vector<pair<int, int> > adj[n + 1];
	int c[n - 1] = {};
	for (int i = 0; i < n - 1; i++) {
		cin >> u >> v;
		adj[u].emplace_back(v, i);
		adj[v].emplace_back(u, i);
	}
	for (int i = 1; i <= n; i++)
		md = max(md, (int)adj[i].size());
	for (int i = 1; i <= n; i++) {
		bool cnt[md + 1] = {};
		int idx = 1;
		for (auto j : adj[i])
			if (c[j.second])
				cnt[c[j.second]] = 1;
		for (auto j : adj[i]) {
			if (!c[j.second]) {
				while (cnt[idx]) idx++;
				c[j.second] = idx;
				cnt[idx] = 1;
			}
		}
	}
	cout << md << '\n';
	for (int i : c) cout << i << '\n';
}


Measured memory_bytes: 6912
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
//#define MOD 998244353
#define INF 1000000010
#define EPS 1e-9
#define F first
#define S second

#define debug(x) cout<<x<<endl;
#define repi(i,x,n) for(int i=x;i<n;i++)
#define rep(i,n) repi(i,0,n)
#define lp(i,n) repi(i,0,n)
#define repn(i,n) for(int i=n;i>=0;i--)
#define int long long
#define endl "\n"

typedef pair<int,int> PII;
typedef pair<int,string> PIS;
typedef pair<string,int> PSI;


signed main(){
  cin.tie(0);	
  ios::sync_with_stdio(false);
  int h;
  cin>>h;
  int a=2;
  while(h!=1){
    h/=2;
    a*=2;
  }
  cout<<a-1<<endl;

  return 0;
}


Measured memory_bytes: 256
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
      	int X = sc.nextInt();
      	int Y = sc.nextInt();
      	boolean ans = false;
      	for(int i=0;i<X+1;i++){
            if( i*2 + (X-i)*4 == Y ){
              ans = true;
            }    
        }
      if( ans ){
        System.out.println("Yes");
      }else{
        System.out.println("No");
      }       
	}
}

Measured memory_bytes: 27072
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define mp make_pair
#define F first
#define S second

signed main(){
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	int n,k;
	cin >> n >> k;
	int arr[n];
	for(int i=0; i<n; i++){
		cin >> arr[i];
	}

	for(int i=0; i<n-k; i++){
		if(arr[k+i]>arr[i]){
			cout << "Yes\n";
		}
		else
			cout << "No\n";
	}


	
	

	return 0;
}

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

using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define erep(i, n) for (ll i = 0; i <= (ll)(n); ++i)
#define FOR(i,a,b) for (ll i = (a); i < (ll)(b); ++i)
#define EFOR(i,a,b) for (ll i = (a); i <= (ll)(b); ++i)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } }



int main() {
    ll h; cin >> h;
    ll ans = 0;
    int now = 0;
    while(h > 0) {
        h /= 2;
        ans += pow(2, now);
        now++;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
using namespace std;
char b, result[30];

int main()
{
    result['A' - 'A'] = 'T';
    result['T' - 'A'] = 'A';
    result['C' - 'A'] = 'G';
    result['G' - 'A'] = 'C';
    scanf("%c", &b);
    printf("%c", result[b - 'A']);
}

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

using namespace std;
typedef long long ll;

ll largemod(ll a,string b);
bool year(int n);
int main(void)
{
int n;
string s,x;
cin>>n>>s;
int ans=0;
for(int i=0;i<n-2;i++)
{
    x=s.substr(i,3);
    if(x=="ABC")
    {
        ans++;
    }
}
cout<<ans<<endl;



}






Measured memory_bytes: 3616
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
 
/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
    sizeは(int)とキャストしよう
    ごちゃごちゃ場合分けを考える前に全探索は考えましたか？
*/
 
const ll mod = 1e9+7;

void chmod(ll &M){
    if(M >= mod) M %= mod;
    else if(M < 0){
        M += (abs(M)/mod + 1)*mod;
        M %= mod;
    }
}

ll modpow(ll x, ll n){
    if(n == 0) return 1;

    ll res = modpow(x, n/2);
    if(n%2 == 0) return res*res%mod;
    else return res*res%mod*x%mod;
}

ll power(ll x, ll n){
    if(n == 0) return 1;

    ll res = power(x, n/2);
    if(n%2 == 0) return res*res;
    else return res*res*x;
}

int getl(int i, int N) { return i==0? N-1:i-1; };
int getr(int i, int N) { return i==N-1? 0:i+1; };

/* <--------------------------------------------> */

typedef tuple<ll, ll, ll> T;

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

    int n, k; cin >> n >> k;
    string s; cin >> s;
    s = '1' + s + '1';

    vector< pair<int,int> > v;
    
    bool zero = true;
    int left;
    if(s[0] == '0') { zero = true; left = 1; }
    else { zero = false; }

    v.push_back(make_pair(0, 0));
    for(int i=1; i<=n+1; ++i){
        if(zero && s[i] == '1'){
            zero = false;
            v.push_back(make_pair(left, i-1));
        }
        else if(!zero && s[i] == '0'){
            zero = true;
            left = i;
        }
    }
    v.push_back(make_pair(n+1, n+1));
    
    if(v.size()-2 <= k){
        cout << n << endl;
        return 0;
    }

    int ans = 0;
    for(int l=1; l<v.size()-k; ++l){
        chmax(ans, v[l+k].first - v[l-1].second - 1);
    }

    cout << ans << endl;

    //for(auto p:v) cout << p.first << ' ' << p.second << endl;

	return 0;
}

Measured memory_bytes: 1020
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int a = sc.nextInt();

		if (1 <= a && a<= 999) {

			System.out.println("ABC");
		} else {
			System.out.println("ABD");
		}
	}
}


Measured memory_bytes: 21844
import java.util.*;
 
public class Main {
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()) {
            String[] sarr = sc.next().split(",");
            int[] x = new int[15];
            for(int i=0;i<12;i++) {
                x[i] = Integer.valueOf(sarr[i]);
            }
            int v1 = x[10];
            int v2 = x[11];
            for(int i=1;i<10;i++) {
                x[i] += x[i-1];
            }
            for(int i=0;i<10;i++) {
                if (x[9]*v1<=x[i]*(v1+v2)) {
                    System.out.println(i+1);
                    break;
                }
            }
        }
    }
 
}

Measured memory_bytes: 17160
using System;
class _1179
{
    public static void Main()
    {
        string str;
        string[] date;
        int n = int.Parse(Console.ReadLine());
        for (int i = 0; i < n; i++)
        {
            str = Console.ReadLine();
            date = str.Split();
            Console.WriteLine(Millennium.Calc(int.Parse(date[0]), int.Parse(date[1]), int.Parse(date[2])));
        }
    }
}
static class Millennium
{
    static int[] DoY = { 195, 200 };
    const int DoLM = 20, DoSM = 19;
    static int count, startDay, month, year;
    public static int Calc(int Y, int M, int D)
    {
        count = 0; startDay = D; year = Y; month = M - 1;
        while (month != 0)
        {
            startDay += (Y % 3 == 0) ? DoLM : ((Y % 3 != 0 && month % 2 == 1) ? DoLM : DoSM);
            month--;
        }
        while (year != 1000)
        {
            count += (year % 3 != 0) ? DoY[0] : DoY[1];
            year++;
        }
        count -= startDay - 1;
        return count;
    }
}

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

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; ++i) cin >> a.at(i);
  sort(a.begin(), a.end());
  cout << a.at(n - 1) - a.at(0) << endl;
}


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

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;


const ll LongINF=1e13+7;
const int INF=1e9+7;
const int dx[]={0,1,0,-1};
const int dy[]={1,0,-1,0};

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;}
template <class T, class Y>T GCD(T a, Y b){if(a<b){int c=a;a=b;b=c;}if (a % b == 0){return b;}return GCD(b, a % b);}
void clear(queue<pair<int, int>> &q){queue<pair<int, int>> empty;swap(q, empty);} //queueの中身の型は適時変更を忘れない

#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define rv reverse
#define ALL(a) (a).begin(),(a).end()


int main(){
    ll A,B;
    cin>>A>>B;

    ll ANS=(A*B)/GCD(A,B);

    cout<<ANS<<endl;

    return 0;
}

//a=97,z=122

Measured memory_bytes: 256
import heapq
n, k = map(int, input().split())
v = list(map(int, input().split()))

result = []
for i in range(min(n, k)+1):
    for j in range(min(n, k)+1-i):
        x = v[:i]+v[n-j:]
        c = k - (i + j)
        x.sort()
        for t in range(min(len(x), c)):
            if x[0]<0:
                x.pop(0)
            else:
                break
        result.append(sum(x))
print(max(result))

Measured memory_bytes: 3188
#include <algorithm>
#include <array>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <utility>
#include <vector>

using namespace std;
using ll = long long;

constexpr ll infl = 1000000000000000007LL;
constexpr int inf = 1000000007;

int main() {
    string table[] = {"SUN","MON","TUE","WED","THU","FRI","SAT" };
    string s; cin >> s;
    for (int i = 0; i < 7; ++i) {
        if (s == table[i]) {
            cout << (7 - i) << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  	int W, a, b;
	cin>>W>>a>>b;
	if(b<a)
		swap(a,b);
	if(b<=a+W)
		cout<<0<<endl;
	else
		cout<<(b-a-W)<<endl;
}

Measured memory_bytes: 3612
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

static int n;

double calc(int day, int win)
{
	static const int cut = 20;
	static double memo[100001][cut];
	
	if(day == 0)
		for(int i = 0; i < n; ++i)
			for(int j = 0; j < cut; ++j)
				memo[i][j] = -1;
	
	double ret = 0;
	double per = 1.0 / (1 << win);
	
	if(n == day || win >= cut)
		return 0;
		
	if(memo[day][win] != -1)
		return memo[day][win];
	
	ret += (calc(day + 1, win + 1) + 1) * per;
	ret += calc(day + 1, 0) * (1 - per);
	
	return memo[day][win] = ret;
}

int main()
{
	while(true) {
		
		scanf("%d", &n);
		
		if(n == 0)
			break;
		
		printf("%f\n", calc(0, 0));
	}
	
	return 0;
}

Measured memory_bytes: 0
#include <cstdio>
#include <cstring>
#include <vector>
#include <deque>
#include <algorithm>
 
using namespace std;
 
int N, M, Q;
int st[200005];
 
int ele(pair<int,int>p)
{
  return p.second - p.first + 1;
}
 
int main()
{
  memset(st, 0, sizeof(st));
  scanf("%d%d%d", &N, &M, &Q);
  deque<pair<int,int> >b;
  b.push_back(make_pair(0, N-1));
 
  int pos = 0, now = 0;
  for(int i=0;i<M;i++){
    int a;
    scanf("%d", &a);
    if(a%2){
      while(a > ele(b.back())){
    a -= ele(b.back());
    b.push_front(b.back());
    b.pop_back();
      }
      pair<int, int>tmp = b.back();
      b.pop_back();
      now = tmp.second - (a-1);
      if(now == tmp.first){
    tmp.first++;
    b.push_front(tmp);
      }else if(now == tmp.second){
    tmp.second--;
    b.push_back(tmp);
      }else{
    b.push_front(make_pair(tmp.second - (a-1) + 1, tmp.second));
    b.push_back(make_pair(tmp.first, tmp.second -  (a-1) - 1 ));    
      }
    }else{
      while(a >= ele(b.front())){
    a -= ele(b.front());
    b.push_back(b.front());
    b.pop_front();
      }
      pair<int,int>tmp = b.front();
      b.pop_front();
      now = tmp.first + a;
      if(now == tmp.first){
    tmp.first++;
    b.push_front(tmp);
      }else if(now == tmp.second){
    tmp.second--;
    b.push_back(tmp);
      }else{
    b.push_back(make_pair(tmp.first, tmp.first + a - 1));
    b.push_front(make_pair(tmp.first + a + 1, tmp.second));
      }
    }
    st[now] = 1;
    now = b.front().first;
    //    for(int j=0;j<b.size();j++) printf("%d:%d ", b[j].first, b[j].second); puts("");
  }
  for(int i=0;i<Q;i++){
    int q;
    scanf("%d", &q);
    printf("%d\n", !st[q]);
  }
  return 0;
}


Measured memory_bytes: 3776
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+5;
char s[N],t[N];
ll n,m,l,g;
int main(){
	scanf("%lld%lld%s%s",&n,&m,s,t);
	g=__gcd(n,m);
	l=n/g*m;
	ll ans=l;
	for(int i=0; i<g; i++){
		if(s[l/m*i]!=t[l/n*i]){
			ans=-1;
			break;
		}
	}
	printf("%lld\n",ans);
	return 0;
}


Measured memory_bytes: 384
using System;

namespace ABC100a
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] str = Console.ReadLine().Split(' ');
            int A = int.Parse(str[0]);
            int B = int.Parse(str[1]);

            if (A<=8&&B<=8)
            {
                Console.WriteLine("Yay!");
            }
            else
            {
                Console.WriteLine(":(");
            }
        }
    }
}


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

int n;
int h[300];       // 最大 200 個なので余裕を持って 210 に --- 200 以上ならなんでもよいです

int main() {
    cin >> n;
//    vector<int> h(n);
    for (int i = 0; i < n; ++i) cin >> h[i];
    int ans = 0;
    int active = 0;

    for(int i = 0; i < n; ++i){
        if(active >= h[i]){
            active = h[i];
        }else{
            ans += h[i] - active;
            active = h[i];
        }
    }

    cout << ans << endl;


}

Measured memory_bytes: 256
def sm(x):
  xls=list(str(x))
  a=0
  for i in range(len(xls)):
    a+=int(xls[i])
  return a
n,a,b=map(int,input().split())
ans=0
for i in range(1,n+1):
  if a<=sm(i)<=b:
    ans+=i
print(ans)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,ans=0;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int a,b;
		cin>>a>>b;
		ans+=b-a+1;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <iomanip>

#include <vector>
#include <set>
#include <bitset>
#include <map>
#include <deque>
#include <string>

#include <algorithm>
#include <numeric>
#include <random>

#include <cstdio>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>

using namespace std;

#define forn(i, n) for (ll i = 0; i < (ll) (n); ++i)
#define sz(a) static_cast<int>((a).size())
#define endl '\n'

using ll = long long;

const ll INF = static_cast<ll>(1e9) + 7;
const int MAXN = static_cast<int>(2e5) + 17;

int n, k;
string s;

bool read() {
    if (!(cin >> s >> k))
        return false;

    return true;
}

void solve() {
    n = sz(s);
    vector<string> t;

    forn (i, n)
        forn (j, k)
            if (i + j <= n)
                t.push_back(s.substr(i, j + 1));

    sort(t.begin(), t.end());
    t.resize(unique(t.begin(), t.end()) - t.begin());
    cout << t[k - 1] << endl;
}

int main() {
    cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    std::mt19937 rand('S' + 'E' + 'R' + 'E' + 'Z' + 'H' + 'K' + 'A');

#ifdef SEREZHKA
    freopen("file.in", "r", stdin);
#endif

    while (read())
        solve();

    return 0;
}


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

#ifdef DEBUG
#include "inc/debug.hpp"
#else
#define debug(...) 42
#endif

int main() {
    string s;
    cin >> s;
    for (int i=0; i<(int)s.size(); ++i) {
        s[i] = 'x';
    }
    cout << s << endl;
    return 0;
}

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

int main(){

  string a,s,t;
  char b;
  int n,an=0;
  cin >> s>>t;
  n=s.length();
  for(int i=0;i<n;i++){
    a=t.substr(0,n-1);
    b=t[n-1];
    t[0]=b;
    for(int i=1;i<n;i++){
      t[i]=a[i-1];
    }
    if(s==t){
      an++;
      cout << "Yes" << endl;
      break;
    }

  }
  if(an==0){
    cout << "No" << endl;
  }
  return 0;


}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 5;
int n;
char s[maxn];
void kmp(char *s, vector<int> &nxt) {
	for(int i = 2, j = 0; i <= n; ++i) {
		while(j && s[j + 1] != s[i]) {
			j = nxt[j];
		}
		if(s[j + 1] == s[i]) {
			++j;
		}
		nxt[i] = j;
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> s + 1;
	n = strlen(s + 1);
	vector<int> f;
	vector<int> g;
	f.resize(n + 1);
	g.resize(n + 1);
	kmp(s, f);
	for(int i = 1; i <= n; ++i) {
		f[i] = i - f[i];
	}
	reverse(s + 1, s + n + 1);
	kmp(s, g);
	for(int i = 1; i <= n; ++i) {
		g[i] = i - g[i];
	}
	if(f[n] == n || n % f[n] != 0) {
		cout << 1 << '\n' << 1 << '\n';
		return 0;
	}
	if(f[n] == 1) {
		cout << n << '\n' << 1 << '\n';
		return 0;
	}
	int ans = 0;
	for(int i = 1; i < n; ++i) {
		if((f[i] == i || i % f[i] != 0) && (g[n - i] == n - i || (n - i) % g[n - i] != 0)) {
			++ans;
		}
	}
	cout << 2 << '\n' << ans << '\n';
	return 0;
}

Measured memory_bytes: 4608
#include<bits/stdc++.h>
using namespace std;
int main(void)
{
	int n,m;
	int a[100001],b[100001],sum[100001];
	int i,j;
	
	cin>>n>>m;
	for(i=1;i<n;i++) {cin>>a[i];}
	for(i=0;i<m;i++) {cin>>b[i];}
	
	int sum1=0;
	sum[0]=0;
	for(i=1;i<n;i++){
		sum1+=a[i],sum[i]=sum1;
	}
	
	int ans=0,pos=0;
	for(i=0;i<m;i++){
		if(b[i]>=0) ans+=sum[pos+b[i]]-sum[pos];
		else ans+=sum[pos]-sum[pos+b[i]];
		ans%=100000;
		pos+=b[i];
	}
	
	cout<<ans<<endl;
	
	return 0;
}	


Measured memory_bytes: 4264
#include <bits/stdc++.h>
#define pt(sth) cout << sth << "\n"
#define chmax(a, b) {if(a<b) a=b;}
#define chmin(a, b) {if(a>b) a=b;}
#define moC(a, s, b) (a)=((a)s(b)+MOD)%MOD
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
static const ll INF=1e18;
static const ll MOD=1e9+7;
static const ll MAX=101010;

/*
 for(i=0; i<N; i++)
   cin >> a[i];
*/


int main(void) {
  ll i, j, k;
  
  ll N;
  cin >> N;
  ll a[MAX], b[MAX], c[MAX];
  
  for(i=0; i<N; i++) cin >> a[i]; sort(a, a+N);
  for(i=0; i<N; i++) cin >> b[i]; sort(b, b+N);
  for(i=0; i<N; i++) cin >> c[i]; sort(c, c+N);
  c[N]=INF;
  
  ll ans=0;
  for(i=0; i<N; i++) {
    ll at=lower_bound(a, a+N, b[i])-a;
    at--;
    if(at<0) continue;
    
    ll ct=upper_bound(c, c+N+1, b[i])-c;
    
    ans+=(at+1)*(N-ct);
    
  }
  
  pt(ans);
}




Measured memory_bytes: 2688
#include<bits/stdc++.h>
#define N 305
using namespace std;
char s[N];
int n,k,dp[N][N][N],Ans;
void upd(int &x,int y)
{
	x=max(x,y);
}
int main()
{
	scanf("%s",s+1);
	n=strlen(s+1);
	scanf("%d",&k);
	dp[1][n][0]=0;
	for (int i=0;i<=k;i++)
	{
		for (int l=1;l<=n;l++)
		for (int r=n;r>=l;r--)
		{
			int tmp=dp[l][r][i];
			
			if (l==r) upd(Ans,tmp+1);
			else
			{
				if (l+1==r)
				{
					if (s[l]==s[r]||i<k) upd(Ans,tmp+2);
					else upd(Ans,tmp+1);
				}
				else
				{
					upd(dp[l+1][r][i],tmp);
					upd(dp[l][r-1][i],tmp);
					if (s[l]==s[r]) upd(dp[l+1][r-1][i],tmp+2);
					else if (i<k) upd(dp[l+1][r-1][i+1],tmp+2);
				}
			}
		}
	}
	printf("%d\n",Ans);
}

Measured memory_bytes: 110464
import java.util.*;

class Main {
    public static void main(String args[]) {
        Scanner inp = new Scanner(System.in);
        String ss = inp.next();
        char s[] = ss.toCharArray();
        int ans = 0;
        for (int i = 0; i < 4; i++) {
            if (s[i] == '+') ans++;
            else ans--;
        }
        System.out.println(ans);
        inp.close();
    }
}


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

int main() {
  int h, w;
  cin >> h >> w;
  vector<string> s(h);
  rep(i,h) cin >> s[i];
  vector<vector<int>> cnt(h, vector<int>(w));
  rep(i,h) {
    vector<int> done(w);
    rep(j,w) {
      if (s[i][j] == '#') continue;
      if (done[j]) continue;
      int l = 0;
      while (j+l < w) {
        if (s[i][j+l] == '#') break;
        ++l;
      }
      rep(k,l) {
        cnt[i][j+k] += l;
        done[j+k] = 1;
      }
    }
  }
  rep(j,w) {
    vector<int> done(h);
    rep(i,h) {
      if (s[i][j] == '#') continue;
      if (done[i]) continue;
      int l = 0;
      while (i+l < h) {
        if (s[i+l][j] == '#') break;
        ++l;
      }
      rep(k,l) {
        cnt[i+k][j] += l;
        done[i+k] = 1;
      }
    }
  }
  int ans = 0;
  rep(i,h)rep(j,w) ans = max(ans, cnt[i][j]-1);
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 20096
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	
	static class AllocStatus {
		int startIdx = 0;
		int startWeight = 0;
	}
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		
		String[] inputs = reader.readLine().split(" ");
		int n = Integer.parseInt(inputs[0]);
		int k = Integer.parseInt(inputs[1]);
		
		int[] weights = new int[n];
		int capacity = 0;
		for (int i = 0; i < n; i++) {
			int weight = Integer.parseInt(reader.readLine());
			weights[i] = weight;
			capacity += weight;
		}

		capacity /= k;
		AllocStatus allocStatus = new AllocStatus();
		while (true) {
			boolean canAllocate = checkAllocation(weights, k, capacity, allocStatus);
			if (canAllocate) {
				break;
			}
			capacity++;			
		}		
		System.out.println(capacity);		
	}

	private static boolean checkAllocation(int[] weights, int k, int capacity, AllocStatus allocStatus) {
		
		int num = 1;
		int current = allocStatus.startWeight;

		for (int i = allocStatus.startIdx; i < weights.length; i++) {
			int weight = weights[i];
			if (current + weight > capacity) {
				if (num == 1) {
					allocStatus.startIdx = i;
					allocStatus.startWeight = current;
				}
				current = weight;
				num++;
				
				if (num > k || current > capacity) {
					return false;
				}
			} else {
				current += weight;
			}
		}
		return true;
	}
}


Measured memory_bytes: 35092
#include<stdio.h>

int search(int A[], int n, int key) {
  int i = 0;
  A[n] = key;
  while ( A[i] != key ) i++;
  return i != n;
}

int main() {
  int i, n, A[10000+1], q, key, sum = 0;

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

  scanf("%d", &q);
  for ( i = 0; i < q; i++ ) {
    scanf("%d", &key);
    if ( search(A, n, key) ) sum++;
  }
  printf("%d\n", sum);

  return 0;
}


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

vector<long int> v[100005];
long int dp[100005];

long int lng(long int i){

	if(v[i].size()==0){
		return 0;
	}
	if(dp[i]!=-1){
		return dp[i];
	}
	else{
		dp[i] = 0;
		for(int j=0;j<v[i].size();j++){
			if(1+lng(v[i][j])>dp[i]){
				dp[i] = 1+lng(v[i][j]);
			}
		}
		return dp[i];
	}
}

int main(){

	long int n,m,x,y;
	cin>>n>>m;
	
	for(long int i=0;i<m;i++){
		cin>>x>>y;
		v[x].push_back(y);
	} 
	long int c=0;
	for(long int i=0;i<100005;i++){
		dp[i]=-1;
	}
	for(long int i=1;i<=n;i++){
		if(lng(i)>c)
			c= lng(i);
	}
	cout<<c<<endl;
	return 0;
}

Measured memory_bytes: 8576
n = int(input())
s = [list(ord(e) - ord("a") for e in input()) for _ in range(n)]

ans = 0
for b in range(n):
    t = [[-1] * n for _ in range(n)]
    for hi in range(n):
        for wi in range(n):
            nh = hi
            nw = (wi + b) % n
            t[nh][nw] = s[hi][wi]

    bl = True
    for i in range(n):
        for j in range(n):
            if t[i][j] != t[j][i]:
                bl = False

    ans += bl

ans *= n
print(ans)


Measured memory_bytes: 123228
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
#define LOOP(i,x,n) for(int i=x;i<n;i++)
#define ALL(v) (v).begin(),(v).end()
#define PB push_back
#define MP make_pair
#define FR first
#define SC second
#define int long long

using namespace std;
const int MOD=1000000007;
const int INF=9000000009;
const double eps=1e-10;

signed main(){
  int n;
  cin>>n;
  vector<int> a(n+1),b(n+1);
  REP(i,n)cin>>a[i+1];
  REP(i,n)cin>>b[i+1];
  REP(i,n){
    a[i+1]+=a[i];
    b[i+1]+=b[i];
  }
  int ans=-INF;
  LOOP(i,1,n+1){
    int tmp=0;
    tmp+=a[i];
    tmp+=b[n]-b[i-1];
    ans=max(ans,tmp);
  }
  cout<<ans<<endl;


  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <math.h>
#include <string>
#include <map>
#include <cstdlib>
using namespace std;

typedef long long ll;

int main()
{
    ll N,X;
    cin >> N >> X;
    ll depth_nums[N+1][2];//深さ総数、パティ数
    depth_nums[0][0]=1;
    depth_nums[0][1]=1;
    for(int i=1; i<=N; i++){
        depth_nums[i][0]=2*depth_nums[i-1][0]+3;
        depth_nums[i][1]=2*depth_nums[i-1][1]+1;
    }
    ll ans=0;
    for(int i=N; i>=0; i--){
        if((depth_nums[i][0]+1)%2==0 && (depth_nums[i][0]+1)/2==X){
            ans+=depth_nums[i][1]/2+1;
            break;
        }else if(depth_nums[i][0]/2>=X) X--;
        else{
            ans+=depth_nums[i][1]/2+1;
            X-=depth_nums[i][0]/2+1;
        }
    }
    cout << ans << endl;
    
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define mod 1000000007
#define ll long long
using namespace std;
ll i,j,k=2,n,m,a[200007],dp[200007];


int main()
{

    cin>>n;
    for(ll i=1;i<=n;i++)
        cin>>a[i];
    for(i=1;i<=n;i++)
    {
        dp[i] = 1e9;
        for(j=1;j<=k&&i-j>0;j++)
        {
            dp[i] = min(dp[i],dp[i-j]+abs(a[i]-a[i-j]));
        }
        if(i==1) dp[i] = 0;
    }
    cout<<dp[n]<<endl;
    return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define debug(val) cerr << "The value of " << #val << " is = " << val << '\n';
typedef long long ll;
typedef long double ld;
const ld pi = 4*atan((ld)1);
const ll mod = 1e9 + 7;
const ll inf = 922337203685477;
const ll nax = 0;

ll x;

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	cin >> x;
	if(x == 1){
		cout << "0\n";
	}
	else if(x == 0){
		cout << "1\n";
	}
}

	


Measured memory_bytes: 3648
#include <bits/stdc++.h>
#define l_ength size
const int inf = (1<<30);
const int mod = 1000000007;
using ll = long long;
using namespace std;

int main(){
	string s; cin >> s;
	string t;
	int bound = s.l_ength();
	for( int i = 0; i < bound; ++i ){
		if( i < bound-1 && s[i] == 'B' && s[i+1] == 'C' ){
			t += 'X';
			++i;
		} else {
			t += s[i];
		}
	}
	bound = t.l_ength();
	ll ans = 0;
	ll acnt = 0;
	for( int i = 0; i < bound; ++i ){
		if( t[i] == 'A' ) ++acnt;
		else if( t[i] == 'X' ) ans += acnt;
		else acnt = 0;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 776
x,y=map(int,input().strip().split())
nums = list(map(int, input().strip().split()))
ans=0
if y==0:
  print(x)
elif x not in nums:
  print(x)
else:
  for i in range(0,102):
    if i not in nums:
      if abs(x-i)<abs(x-ans):
        ans=i
  print(ans)

Measured memory_bytes: 9196
import java.util.*;
import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        // Your code here!
        Scanner sc = new Scanner(System.in);
        
        int a = sc.nextInt();
        int b = sc.nextInt();
        
        double ad = (double)a;
        double bd = (double)b;
        
        
        
        System.out.print(a/b + " "+ a%b +" ");
        System.out.printf("%.5f\n", ad/bd);

    }
}



Measured memory_bytes: 26600
import Data.Array
import Data.List
import qualified Data.Vector.Unboxed as V

main = do
  n <- readLn
  ps <- V.replicateM n $ do
    [x, y] <- map read . words <$> getLine :: IO [Int]
    return (x, y)
  let dist (x1, y1) (x2, y2) = sqrt . fromIntegral $ ((x1 - x2) ^ 2) + ((y1 - y2) ^ 2)
  let dists = array ((0,0), (n-1, n-1)) [((i, j), dist (ps V.! i) (ps V.! j)) | i <- [0..n-1], j <- [0..n-1]]
  print $ solve n dists


solve :: Int -> Array (Int, Int) Double -> Double
solve n dists = (/ (fromIntegral (product [1..n]))) . sum . map go . permutations $ [0..n-1]
  where
    go [] = 0
    go (i:[]) = 0
    go (i:j:ps) = dists ! (i, j) + go (j:ps)

Measured memory_bytes: 2172
number = list(map(int, input().split()))
#print(number[0])
#print(number[1])

if 1 <= number[0] and number[0] <= 9:
  if 1 <= number[1] and number[1] <= 9:
    print(number[0] * number[1])
  else:
    print('-1')
else:
  print('-1')

Measured memory_bytes: 3060
import sys
input = sys.stdin.readline
n = int(input())
A = list(map(int,input().split()))
B = [0] * (n+1)
for i in range(n):
    B[A[i]] += 1

C = [0] * (n+1)
for i in range(n+1):
    C[i] = B[i]*(B[i]-1)//2

su = sum(C)

for i in range(n):
    print(su - C[A[i]] + (B[A[i]]-1)*(B[A[i]]-2)//2)

Measured memory_bytes: 79564
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <tuple>
#include <bitset>
#include <memory>
#include <cmath>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <numeric>
#include <climits>
#include <cfloat>


int main() {
	int n, q; std::cin >> n >> q;
	std::vector<std::vector<int>> nodes(n);
	for (auto i = 1; i < n; ++i) {
		int a, b; std::cin >> a >> b; --a; --b;
		nodes[a].push_back(b);
	}
	std::vector<std::pair<int, int>> in_euler(n);
	std::stack<std::pair<bool, int>> stack; stack.emplace(true, 0);
	for (auto i = 0; i < 2 * n; ++i) {
		auto top = stack.top(); stack.pop();
		if (top.first) {
			in_euler[top.second].first = i;
			stack.emplace(false, top.second);
			for (const auto& next : nodes[top.second]) {
				stack.emplace(true, next);
			}
		}
		else {
			in_euler[top.second].second = i;
		}
	}
	std::vector<long long int> imos(2 * n, 0);
	for (auto i = 0; i < q; ++i) {
		int p, x; std::cin >> p >> x;
		imos[in_euler[--p].first] += x;
		imos[in_euler[p].second] -= x;
	}
	for (auto i = 1; i < imos.size(); ++i) imos[i] += imos[i - 1];
	for (auto i = 0; i < n; ++i) {
		if (i != 0) std::cout << ' ';
		std::cout << imos[in_euler[i].first];
	}
	std::cout << std::endl;
}



Measured memory_bytes: 19128
#include<cstdio>
#include<algorithm>
#include<numeric>
#include<functional>

using namespace std;

int main(){
	int n, k; scanf("%d %d", &n, &k);
	int l[50];
	for(int i = 0; i < n; i++) scanf("%d", &l[i]);
	sort(l, l + n, greater<int>());
	printf("%d\n", accumulate(l, l + k, 0));
	return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<iomanip>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<functional>
#include<map>
#include<cstdlib>
#include<complex>
#include<numeric>
#include<set>
#include<deque>
#include<queue>

using namespace std;
using Int = long long;
Int INF = 1LL << 60;
const Int MOD = 1000000000 + 7;

template <class T>
ostream& operator<<(ostream& os, const vector<T>& vec) {
	for (const auto& e : vec) os << e << (&e == &vec.back() ? "\n" : " ");
	return os;
}
template <class T>
ostream& operator<<(ostream& os, const set<T>& st) {
	for (const auto& e : st) os << e << " ";
	return os;
}
template <class T1, class T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
	os << "(" << p.first << "," << p.second << ")";
	return os;
}
template <class T1, class T2>
ostream& operator<<(ostream& os, const map<T1, T2>& mp) {
	for (const auto& e : mp) os << e << " ";
	return os;
}

#ifdef _DEBUG
template <class T>
void dump(const char* str, T&& h) { cerr << str << " = " << h << "\n"; };
template <class Head, class... Tail>
void dump(const char* str, Head&& h, Tail&&... t) {
	while (*str != ',') cerr << *str++; cerr << " = " << h << "\n";
	dump(str + (*(str + 1) == ' ' ? 2 : 1), t...);
}
#define DMP(...) dump(#__VA_ARGS__, __VA_ARGS__)
#else 
#define DMP(...) ((void)0)
#endif

int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	Int N, K, R, S, P;
	string T;
	cin >> N >> K >> R >> S >> P >> T;

	vector<vector<Int>> dp(N+1, vector<Int>(3));
	if (T[0]=='s') {
		dp[0][0] = R;
	}
	else if (T[0]=='r') {
		dp[0][2] = P;
	}
	else {
		dp[0][1] = S;
	}

	for (Int i = 0; i < K; i++) {
		if (T[i] == 's') {
			dp[i+1][0] = R;
		}
		else if (T[i] == 'r') {
			dp[i+1][2] = P;
		}
		else {
			dp[i+1][1] = S;
		}
	}

	for (Int i = 0; i < K; i++) {
		Int temp = K;
		while (temp+i+1<=N) {
			//グーを出す場合
			if (T[i+temp]=='s') {
				dp[i + temp + 1][0] = max(dp[i + (temp - K) + 1][1] + R, dp[i + (temp - K) + 1][2] + R);
			}
			else  {
				dp[i + temp + 1][0] = max(dp[i + (temp - K) + 1][1], dp[i + (temp - K) + 1][2]);

			}

			//チョキを出す場合
			if (T[i+temp]=='p') {
				dp[i + temp + 1][1] = max(dp[i + (temp - K) + 1][0] + S, dp[i + (temp - K) + 1][2] + S);

			}
			else {
				dp[i + temp + 1][1] = max(dp[i + (temp - K) + 1][0] , dp[i + (temp - K) + 1][2] );

			}

			//パーを出す場合
			if (T[i+temp]=='r') {
				dp[i + temp + 1][2] = max(dp[i + (temp - K) + 1][0] + P, dp[i + (temp - K) + 1][1] + P);

			}
			else {

				dp[i + temp + 1][2] = max(dp[i + (temp - K) + 1][0], dp[i + (temp - K) + 1][1]);

			}

			temp += K;
		}
	}

	DMP(dp);

	Int ans = 0;
	for (Int i = N; i >= N-K+1; i--) {
		ans += max({ dp[i][0],dp[i][1],dp[i][2] });
	}
	cout << ans << "\n";
}


Measured memory_bytes: 5840
package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	cnt := 0
	for i:=0; i<n/4+1; i++ {
		for j:=0; j<n/7+1; j++ {
			if i*4 + j*7 == n {
				cnt += 1
			}
		}
	}
	if cnt > 0 {
		fmt.Println("Yes")
	}else{
		fmt.Println("No")
	}
}


Measured memory_bytes: 512
use v5.18; # strict say state
use warnings;
use List::Util qw(reduce first max min sum0);

chomp (my ($n, $m) = split / /, <STDIN>);
chomp (my @a = split / /, <STDIN>);
@a = sort { $b <=> $a } @a;
my $sum = sum0(@a);
my $ans = "Yes";
for my $i (0..$m-1) {
  $ans = "No" if $sum/(4*$m) > $a[$i];
}
say $ans;

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#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=(b)-1; i>=(a); --i)

#define DEBUG(x) cout<<#x<<": "<<x<<'\n'
#define DEBUG_VEC(v) cout<<#v<<":";REP(i, v.size())cout<<' '<<v[i];cout<<'\n'
#define ALL(a) (a).begin(), (a).end()

#define CHMIN(a, b) a=min((a), (b))
#define CHMAX(a, b) a=max((a), (b))

const ll MOD=1000000007ll;
// const ll MOD=998244353ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

const double EPS=1e-11;
#define EQ0(x) (abs((x))<EPS)
#define EQ(a, b) (abs((a)-(b))<EPS)

const ll INF=1e18;
const int MAX_E=2525;
const int MAX_V=1252;

struct edge {
	int from;
	int to;
 	ll cost;
};

// 辺
edge es[MAX_E];

// 最短距離
ll d[MAX_V];
int V, E;

bool shortest_path(int s){
	fill(d, d+V, INF);
	d[s]=0;
	REP(i, V){
		bool update=false;
		REP(j, E){
			edge e=es[j];
			if(d[e.from]!=INF && d[e.to]>d[e.from]+e.cost){
				d[e.to]=d[e.from]+e.cost;
				update=true;
				if(i==V-1 && e.to==V-1){
					return false;
				}
			}
		}
		if(!update){
			break;
		}
	}
	return true;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m, a, b;
	ll c;
	cin>>n>>m;
	V=n;
	E=m;
	REP(i, m){
		edge e;
		cin>>a>>b>>c;
		e.from=a-1;
		e.to=b-1;
		e.cost=-c;
		es[i]=e;
	}
	if(shortest_path(0)){
		cout<<-d[n-1]<<'\n';
	}
	else{
		cout<<"inf"<<'\n';
	}
	return 0;
}


Measured memory_bytes: 256
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N = INT()
L = LIST()

ans = 0
for x in combinations(L, 3):
	if len(set(x)) == 3 and max(x) < sum(x)-max(x):
		ans += 1

print(ans)


Measured memory_bytes: 10564
first = True
while True:
    a, b = map(int, input().split())
    if a == b == 0: break

    if not first: print()
    first = False

    count = 0
    for y in range(a, b + 1):
        if y % 400 == 0 or y % 4 == 0 and y % 100 != 0:
            count += 1
            print(y)
    if count == 0: print('NA')

Measured memory_bytes: 6720
var input = require('fs').readFileSync('/dev/stdin', 'utf8');
var arr=input.trim().split("\n");
var nrl=arr.shift().split(" ").map(Number);
var n=nrl[0];
var L=nrl[2];
var t=[];
var max=[0,0];
var time=0;
for(var i=0;i<n;i++)t[i]=[0,0,i];
arr.push([1,L,0].join(" "));
for(var i=0;i<arr.length;i++){
   var v=arr[i].split(" ").map(Number);
   var d=v[0]-1;
   var T=v[1];
   var x=v[2];
   t[max[0]][1]+=T-time;
   time=T;
   t[d][0]+=x;
   if(x>0){
      if(t[d][0]>max[1])max=[d,t[d][0]];
      else if(t[d][0]==max[1] && d<=max[0])max=[d,t[d][0]];
   }
   else if(x<0 && max[0]==d){
      var MAX=0;
      var m=0;
      for(var j=0;j<t.length;j++){
         if(MAX<t[j][0]){m=j;MAX=t[j][0];}
      }
      max=[m,t[m][0]];
   }
}
t.sort(function(a,b){
   if(a[1]==b[1])return a[2]-b[2];
   else return b[1]-a[1];
});
console.log(t[0][2]+1);

Measured memory_bytes: 126516
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
#include<complex>
using namespace std;

#define rep(i,x) for(ll i=0;i<x;i++)
#define repn(i,x) for(ll i=1;i<=x;i++)

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 1000000007;
const ll MAX = 4000001;
const long double eps = 1E-14;

ll max(ll a, ll b) {
	if (a > b) { return a; }
	return b;
}

ll min(ll a, ll b) {
	if (a > b) { return b; }
	return a;
}

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

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

struct edge {
	ll ind;
	ll fr;
	ll to;
	ll d;
};

class mint {
	long long x;
public:
	mint(long long 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;
	}

	friend ostream& operator<<(ostream& os, const mint& m) {
		os << m.x;
		return os;
	}
};

mint pw(mint a, ll b) {
	if (b == 0) { return 1; }
	mint ret = pw(a, b >> 1);
	ret *= ret;
	if (b & 1) { ret *= a; }
	return ret;
}

typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<vector<vector<ll>>> vvvll;

typedef vector<mint> vmint;
typedef vector<vector<mint>> vvmint;
typedef vector<vector<vector<mint>>> vvvmint;

//////////////////////////////////////

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

	vvll a(N, vll(N));
	rep(i, N)rep(j, N) cin >> a[i][j];

	vll gr(1 << N, 0);

	rep(b, 1 << N) {
		rep(i, N)for (ll j = i + 1; j < N; j++) {
			if ((b >> i) & 1 && (b >> j) & 1) { gr[b] += a[i][j]; }
		}
	}

	vll dp(1 << N, -INF);
	dp[0] = 0;

	rep(i, 1<<N) {
		for (ll j = i; j > 0; j = (j - 1) & i) {
			dp[i] = max(dp[i], gr[j] + dp[i ^ j]);
		}
	}

	cout << dp[(1 << N) - 1] << endl;
}

Measured memory_bytes: 4280