akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define REP(i, n) for(ll i = 0; i < (ll)n; i++)
#define FOR(i, a, b) for(ll i = (a); i < (ll)b; i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define INF (1ll << 60)
#define sz(x) int(x.size())
using namespace std;
template <typename T>
using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
typedef long long ll;
using vl = vector<ll>;
using vvl = vector<vl>;
typedef double db;
typedef string str;
typedef pair<ll, ll> p;
constexpr int MOD = 1000000007;
using ll = long long;
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 print(const std::vector<ll> &v) {
    std::for_each(v.begin(), v.end(), [](ll x) { std::cout << x << " "; });
    std::cout << std::endl;
}
double to_deg(double r) { return r * 180.0 / (atan(1.0) * 4.0); }

int main() {
    ll N;
    ll K;
    cin >> N >> K;
    vector<ll> A(N);
    vector<ll> S(N + 1, 0);
    REP(i, N) { cin >> A[i]; }
    REP(i, N) {
        S[i + 1] = S[i] + A[i];
        S[i + 1] %= K;
    }
    // S[i] - S[j] == i - j
    // S[i] - i = S[j] - j;
    REP(i, N + 1) {
        S[i] = (S[i] - i) % K;
        if(S[i] < 0) {
            S[i] += K;
        }
    }
    // print(S);
    map<ll, ll> cnt;
    queue<ll> que;
    ll ans = 0;
    REP(r, N + 1) {
        ans += cnt[S[r]];
        cnt[S[r]]++;
        que.push(S[r]);
        if(que.size() >= K) {
            cnt[que.front()]--;
            que.pop();
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 17536
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define sync ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define MOD  1000000007 
#define lld long long
lld powm(lld base,lld exp,lld mod=MOD) {lld ans=1;while(exp){if(exp&1) ans=(ans*base)%mod;exp>>=1,base=(base*base)%mod;}return ans;}
int32_t main()
{
	sync
	int n,m;
	cin>>n>>m;
	vector<pair<int,int>>v;
	for(int i=0;i<n;i++)
	{
		int a,b;
		cin>>a>>b;
		v.push_back({a,b});
	}
	sort(v.begin(),v.end());
	priority_queue<int>q;
	int ans=0;
	int k=0;
	for(int i=1;i<=m;i++)
	{
		while(k<n && v[k].first<=i)
		{
			q.push(v[k].second);
			k++;
		}
		if(!q.empty())
		{
			ans+=q.top();
			q.pop();
		}
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 3696
#include "bits/stdc++.h"
using namespace std;
using ll     = long long;
using pii    = pair<int, int>;
using pll    = pair<ll, ll>;
using vi     = vector<int>;
using vl     = vector<ll>;
using vvi    = vector<vi>;
using vvl    = vector<vl>;
const ll INF = 1LL << 60;
const ll MOD = 1000000007;
template <class T>
bool chmax(T &a, const T &b) {
    return (a < b) ? (a = b, 1) : 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    return (b < a) ? (a = b, 1) : 0;
}
template <class C>
void print(const C &c, std::ostream &os = std::cout) {
    std::copy(std::begin(c), std::end(c), std::ostream_iterator<typename C::value_type>(os, " "));
    os << std::endl;
}

vector<vector<int>> nextidx(const string &s) {
    int n = s.size();
    vector<vector<int>> ret(n + 1, vector<int>(26, n));
    for (int i = n - 1; i >= 0; --i) {
        for (int j = 0; j < 26; ++j)
            ret[i][j] = ret[i + 1][j];
        ret[i][s[i] - 'a'] = i;
    }
    return ret;
}

int main() {
    string s;
    cin >> s;
    int n         = s.size();
    auto nxt      = nextidx(s);
    const int inf = 1 << 29;
    vi dp(n + 1, inf);
    vector<pair<char, int>> rec(n + 1, {'?', n});
    for (int i = n - 1; i >= 0; --i) {
        for (int j = 0; j < 26; ++j) {
            if (nxt[i][j] == n) {
                if (dp[i] > 1) {
                    dp[i]  = 1;
                    rec[i] = {'a' + j, n};
                }
            } else if (chmin(dp[i], dp[nxt[i][j] + 1] + 1))
                rec[i] = {'a' + j, nxt[i][j] + 1};
        }
    }
    string ret = "";
    int idx    = 0;
    while (idx < n) {
        auto p = rec[idx];
        ret += p.first;
        idx = p.second;
    }
    cout << ret << "\n";
    return 0;
}

Measured memory_bytes: 29316
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
ans = sum(A)
A = Counter(A)
bc = [tuple(map(int, input().split())) for i in range(Q)]
for b, c in bc:
    v = A.pop(b, None)
    if v:
        A[c] += v
        ans = ans+((c-b)*v)
    print(ans)


Measured memory_bytes: 101456
#include<iostream>
#include<vector>
#include<stdlib.h>
#include<time.h>
#include<math.h>
#include<string.h>
#include<algorithm>
#include<queue>
#include<map>
#include<iomanip>
using namespace std;

int main(void){
 int N,Q,l,r;
 int  cnt[200000];
 char S[200000];

 cin>>N>>Q;
 cin>>S;

 for(int i=0; i<200000; i++)cnt[i]=0;

 for(int i=1; i<200000; i++){
  if(S[i-1]=='A' && S[i]=='C')cnt[i]=cnt[i-1]+1;
  else cnt[i]=cnt[i-1];
 }
 
 for(int i=0; i<Q; i++){
  cin>>l>>r;
  cout<<cnt[r-1]-cnt[l-1]<<endl;
 }

 return 0;
}


Measured memory_bytes: 1664
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cassert>
#include <iostream>
#include <cctype>
#include <sstream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <utility>
#include <numeric>
#include <algorithm>
#include <iterator>
#include <bitset>
#include <complex>
#include <fstream>
#include <iomanip>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
template<class T> T RoundOff(T a){ return int(a+.5-(a<0)); }
template<class T, class C> void chmax(T& a, C b){ if(a < b) a = b; }
template<class T, class C> void chmin(T& a, C b){ if(b < a) a = b; }
template<class T, class C> pair<T, C> mp(T a, C b){ return make_pair(a, b); }

double cut(double x)
{	return x - floor(x);	}
int main()
{
	double n;
	while(cin >> n && 0 <= n)
	{
		vector<char> na, de;

		for(int i = n; i; i /= 2)
			na.push_back(i % 2 + '0');

		int lim = 0;
		for(double i = n; lim < 8; i = cut(i) * 2, lim++)
			if(lim)
			{
				de.push_back((1 <= i) + '0');
				if(floor(i) == i) break;
			}

		if(8 < na.size() || 4 < de.size())
			cout << "NA" << endl;
		else
		{
			while(na.size() < 8)
				na.push_back('0');
			while(de.size() < 4)
				de.push_back('0');

			reverse(ALL(na));

			rep(i, 8)
				cout << na[i] << (i == 7 ? "." : "");
			rep(i, 4)
				cout << de[i] << (i == 3 ? "\n" : "");
		}
	}
}

Measured memory_bytes: 0
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
static const int NMAX = 100;
#define INF (1 << 30)
int ADJ[NMAX][NMAX];

int main() {
  int n;
  cin >> n;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      ADJ[i][j] = INF;

  for (int i = 0; i < n; i++) {
    int id, nn;
    cin >> id  >> nn;
    for (int j = 0; j < nn; j++) {
      int to, weight;
      cin >> to >> weight;
      ADJ[id][to] = weight;
    }
  }

  bool visited[n];
  int dist[n];

  // add node 0
  for (int i = 0; i < n; i++) {
    dist[i] = ADJ[0][i];
    visited[i] = false;
  }
  visited[0] = true;
  dist[0] = 0;

  while (true) {
    int minnode = -1;
    int mincost = INF;
    // find nearest node
    for (int i = 0; i < n; i++) {
      if (visited[i] == false && dist[i] < mincost) {
        minnode = i;
        mincost = dist[i];
      }
    }
    if (minnode == -1)
      break;

    // add node
    visited[minnode] = true;

    // update dist
    for (int i = 0; i < n; i++) {
      if (visited[i] == false)
        dist[i] = min(dist[i], dist[minnode] + ADJ[minnode][i]);
    }
  }

  for (int i = 0; i < n; i++)
    cout << i << " " << dist[i] << endl;
}

Measured memory_bytes: 3088
import java.util.*;

public class Main {
 	public static void main(String[] args) {
      
      Scanner sc = new Scanner(System.in);
      
      int loop;
      loop = sc.nextInt();
      
      int [] arr_i = new int [loop];
      
      for(int i = 0; i < loop; i++) {
        	arr_i[i] = sc.nextInt();
      }
      
      sc.close();
     
      ArrayList<Integer> arr_num = new ArrayList<Integer>();
      
     for(int i = 0; i < loop; i++) {
      	if(arr_i[i] % 2 == 0) {
           arr_num.add(arr_i[i]);
        }
     }
      
     int g = 0;
     int ng = 0;
     for(Integer i : arr_num) {
      		if(i % 3 == 0 || i % 5 == 0) {
             	  g++;
            } else {
                  ng++;
            }
     }
      
     if(ng > 0) {
        System.out.print("DENIED");
     } else {
        System.out.print("APPROVED");
     }
     

	}
}


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

using namespace std;

int main(){
	int w,h,n;
	cin >> w >> h >> n;
	int x[n],y[n],a[n];
	for(int i=0; i<n; i++) cin >> x[i] >> y[i] >> a[i];

	int ox = 0;
	int oy = 0;
	int px = w;
	int py = h;

	for(int i=0; i<n; i++){
		if(a[i] == 1) ox = max(ox,x[i]);
		else if(a[i] == 2) px = min(px,x[i]);
		else if(a[i] == 3) oy = max(oy,y[i]);
		else if(a[i] == 4) py = min(py,y[i]);
	}
	if(px>ox && py>oy) cout << (px-ox)*(py-oy) << endl;
	else cout << 0 << endl;

	
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define REP(i,a) FOR(i,0,a)
ll N;
int main(){
	cin.tie(0);
	cin.sync_with_stdio(false);
	cin>>N;
	ll ans=0;
	FOR(i,1,N+1){
		if(i%3>0&&i%5>0){
			ans+=i;
		}
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 3648
N = gets.to_i
H = gets.split.map(&:to_i)

max_count = 0
current_count = nil

H.each_cons(2) do |prev, x|
  next(current_count = nil) if prev < x
  current_count = current_count ? current_count.next : 1
  max_count = current_count if max_count < current_count
end

puts max_count

Measured memory_bytes: 8580
#ABC131-B

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7

def LI(): return list(map(int,input().split()))
def I(): return int(input())
def LS(): return input().split()
def S(): return input()

def main():
  n,l=LI()

  a=[]
  for i in range(n):
    a.append(l+i)

  sm=sum(a)

  mn=inf
  mn_i=-1
  for i in range(n):
    x=a[i]
    if mn>abs(x):
      mn=abs(x)
      mn_i=i

  return sm-a[mn_i]

print(main())


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

template <class T>
bool chmax(T &a, T b)
{
	if (a < b)
	{
		a = b;
		return true;
	}
	return false;
}

template <class T>
bool chmin(T &a, T b)
{
	if (a > b)
	{
		a = b;
		return true;
	}

	return false;
}

const int MAX_N = 1e5 + 10;
const long long INF = 1LL << 60;

int n, k, h[MAX_N];
long long dp[MAX_N];

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

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

	dp[0] = 0;
	for (int i = 0; i < n; ++i)
	{
		for (int j = 1; j <= k; ++j)
		{
			chmin(dp[i + j], dp[i] + abs(h[i] - h[i + j]));
		}
	}

	cout << dp[n - 1] << endl;
}

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

signed main(){
	ll n, C; cin >> n >> C;
	vector<ll> x(n, 0), c(n, 0), x1(n), c1(n), q(n);
	for(int i = 0; i < n; i++){
		cin >> x[i] >> c[i]; q[i] = c[i];
		x1[i] = C - x[i]; c1[i] = c[i];
	}
	reverse(x1.begin(), x1.end());
	reverse(c1.begin(), c1.end());
	for(int i = 1; i < n; i++){
		c[i] += c[i - 1];
		c1[i] += c1[i - 1];
	}
	vector<ll> data1(n + 1, 0), data2(n + 1, 0);
	for(int i = 1; i <= n; i++){
		data1[i] = c[i - 1] - x[i - 1];
		data2[i] = c1[i - 1] - x1[i - 1];
	}
	vector<ll> data_left(n + 1, 0), data_right(n + 1, 0);
	for(int i = 1; i  <= n; i++){
		data_left[i] = max(data_left[i - 1], data1[i]);
		data_right[i] = max(data_right[i - 1], data2[i]);
	}
	ll ans = 0;
	for(int left = 0; left <= n; left++){
		if(left == 0) ans = max(ans, data_right[n]);
		ans = max(ans, data1[left] - x[left - 1] + data_right[n - left]);
	}
	for(int right = 0; right <= n; right++){
		if(right == 0) ans = max(ans, data_left[n]);
		else ans = max(ans, data2[right] - x1[right - 1] + data_left[n - right]);
	}
	cout << ans << endl;
}

Measured memory_bytes: 10388
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <algorithm>	// require sort next_permutation count __gcd reverse etc.
#include <cstdlib>	// require abs exit atof atoi 
#include <cstdio>		// require scanf printf
#include <functional>
#include <numeric>	// require accumulate
#include <cmath>		// require fabs
#include <climits>
#include <limits>
#include <cfloat>
#include <iomanip>	// require setw
#include <sstream>	// require stringstream 
#include <cstring>	// require memset
#include <cctype>		// require tolower, toupper
#include <fstream>	// require freopen
#include <ctime>		// require srand
#define rep(i,n) for(int i=0;i<(n);i++)
#define ALL(A) A.begin(), A.end()

using namespace std;

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

const int dr[] = { -1, 0, 1, 0 };
const int dc[] = {  0, 1, 0,-1 }; 

bool v[3003][3003];

int compress (vector<int>& x1, vector<int>& x2, int maxlen )
{
	vector<int> xs; xs.clear();
	xs.push_back (0 );
	xs.push_back (maxlen );
	int n = x1.size();
	rep (i, n ){
		for (int d = -1; d <= 1; d++ ){
			if (x1[i] + d >= 0 && x1[i] + d <= maxlen )
				xs.push_back (x1[i] );
			if (x2[i] + d >= 0 && x2[i] + d <= maxlen )
				xs.push_back (x2[i] );
		} // end for
	} // end for
	sort (ALL (xs ) );
	xs.erase (unique (ALL (xs ) ), xs.end() );
	rep (i, n ){
		x1[i] = lower_bound (ALL (xs ), x1[i] ) - xs.begin();
		x2[i] = lower_bound (ALL (xs ), x2[i] ) - xs.begin();
	} // end rep

	return xs.size();
}

void bfs (int row, int col, int h, int w )
{
	queue<P> que;
	que.push (P (row, col ) );
	while (!que.empty() ){
		P curr = que.front(); que.pop();
		int cr = curr.first;
		int cc = curr.second;
		rep (k, 4 ){
			int nr = cr + dr[k];
			int nc = cc + dc[k];
			if (nr < 0 || nr >= h || nc < 0 || nc >= w ) continue;
			if (v[nr][nc] ) continue;
			que.push (P (nr, nc ) );
			v[nr][nc] = true;
		} // end rep
	} // end while
}

int main()
{
//	cut here before submit 
//	freopen ("testcase.paint_color", "r", stdin );
	int w, h;
	while (scanf ("%d %d", &w, &h ), w, h ){
		memset (v, false, sizeof (v ) );
		int n;
		scanf ("%d", &n );
		vector<int> x1 (n, 0 ), y1 (n, 0 ), x2 (n, 0 ), y2 (n, 0 );
		rep (i, n ){
			scanf ("%d %d %d %d", &x1[i], &y1[i], &x2[i], &y2[i] );
		} // end rep
		w = compress (x1, x2, w );
		h = compress (y1, y2, h );
		rep (i, h ) v[i][w-1] = true;
		rep (j, w ) v[h-1][j] = true;

		rep (i, n ){
			for (int y = y1[i]; y < y2[i]; y++ ){
				for (int x = x1[i]; x < x2[i]; x++ ){
					v[y][x] = true;
				} // end for
			} // end for
		} // end for

		int res = 0;
		rep (i, h ){
			rep (j, w ){
				if (!v[i][j] ){
					v[i][j] = true;
					res++;
					bfs (i, j, h, w  );
				} // end if
			} // end rep
		} // end rep

		printf ("%d\n", res );
	} // end loop
		
	return 0;
}

Measured memory_bytes: 10040
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int N, K;
    cin >> N >> K;
    string S;
    cin >> S;

    vector<int> Nums;
    int now = 1;
    int cnt = 0;
    for(int i = 0; i < N; i++){
        if(S[i] == (char)('0' + now)) 
            cnt++;
        else {
            Nums.push_back(cnt);
            now = 1-now;
            cnt = 1;
        }
    }
    if(cnt != 0)
        Nums.push_back(cnt);

    if(Nums.size()%2 == 0)
        Nums.push_back(0);

    vector<int> sum(Nums.size()+1);
    for(int i = 0; i < Nums.size(); i++){
        sum[i+1] = sum[i] + Nums[i];
    }
    int Add = 2*K+1;
    int ans = 0;

    for(int i = 0; i < Nums.size(); i+=2){
        int left = i;
        int right = min(i+Add, (int)Nums.size());
        int tmp = sum[right] - sum[left];

        ans = max(tmp, ans);
    }

    cout << ans << endl;
}

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

int main(){
  string A, B;
  cin >> A >> B;
  if(A.size()<B.size()){
    cout << "LESS" << endl;
    return 0;
  }
  if(A.size()>B.size()){
    cout << "GREATER" << endl;
    return 0;
  }
  if(A>B){
    cout << "GREATER" << endl;
    return 0;
  }else if(A<B){
    cout << "LESS" << endl;
    return 0;
  }
  cout << "EQUAL" << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
//define
#define int long long
#define rep(x,y) for(int i=x;i<y;i++)
#define REP(x,y) for(int j=x;j<y;j++)
#define Rep(x,y) for(int k=x;k<y;k++)
#define str string
#define pb() push_back()
#define all(x) x.begin(),x.end()
#define elif else if
#define mod 100000007
//vectordefine
#define vint vector<int>
#define vvint vector<vector<int>>
#define vc vector<char>
#define vvc vector<vector<char>>
#define vool vector<bool>
#define vtr vector<str>
#define vvtr vector<vector<str>>
//queuedefine
#define qint queue<int>
#define qtr queue<string>
#define qc queue<char>
//pairdefine
#define pint pair<int,int>
#define pic pair<int,char>
#define pci pair<char,int>
#define pis pair<int,str>
#define psi pair<str,int>
#define pcc pair<char,char>
#define pss pair<str,str>
#define mp make_pair
//mapdefine
#define mint map<int,int>
#define mic map<int,char>
#define mci map<char,int>
#define mis map<int,str>
#define msi map<str,int>
//function
str shizuku(char,char);
//UnionFind

struct UnionFind{
  vint par;
  UnionFind(int N):par(N){
    rep(0,N)par[i]=i;
  }
  int root(int x){
    if(par[x]==x)return x;
    return par[x]=root(par[x]);
  }
  void unite(int x,int y){
    int rx=root(x);
    int ry=root(y);
    if(rx==ry)return;
    par[rx]=ry;
  }
  bool same(int x,int y){
    return root(x)==root(y);
  }
};
//binary_search

//main
signed main(){
    int N,M,X,count=0,count2=0,k=0;
    double d,D;
    int alph='A'-'a';
    char op,Ch;
    str S,T;
    cin>>S;
    rep(0,3){
      if(S[i]==S[i+1])count+=1;
    }
    if(count>=1)cout<<"Bad"<<endl;
    else cout<<"Good"<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  long long N, P;
  cin >> N >> P;
  long long ans = 1;
  for (long long i = 2; i * i <= P; i++){
    if (P % i == 0){
      int cnt = 0;
      while (P % i == 0){
        P /= i;
        cnt++;
      }
      for (int j = 0; j < cnt / N; j++){
        ans *= i;
      }
    }
  }
  if (N == 1){
    ans *= P;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
H, W = map(int, input().split())
AB = []
max_ab = 0
for i in range(H):
  AB.append(list(map(int, input().split())))
  max_ab = max(max_ab, max(AB[-1]))

for i in range(H):
  AB[i] = [abs(AB[i][j] - int(b)) for j, b in enumerate(input().split())]

base = max_ab*(H + W)
dp = [[1 << base for w in range(W)] for h in range(H)]
dp[0][0] = (1 << base + AB[0][0]) | (1 << base - AB[0][0])
for h in range(1, H):
  dp[h][0] = (dp[h-1][0] << AB[h][0]) | (dp[h-1][0] >> AB[h][0])

for w in range(1, W):
  dp[0][w] = (dp[0][w-1] << AB[0][w]) | (dp[0][w-1] >> AB[0][w])

for h in range(1, H):
  for w in range(1, W):
    dp[h][w] = (
      (dp[h-1][w] << AB[h][w]) | (dp[h-1][w] >> AB[h][w]) 
      | (dp[h][w-1] << AB[h][w]) | (dp[h][w-1] >> AB[h][w]))

positive = bin(dp[H-1][W-1] >> base)
print(positive[::-1].find('1'))

Measured memory_bytes: 19828
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("-O3")

long long int knapsack(vector<long long int>& wt, vector<long long int>& val, int n, int Weight, long long int sum){
    vector<vector<long long int>> dp(n+1, vector<long long int>(sum+1, INT_MAX));
    dp[0][0] = 0;
    long long int ans = 0;
    for(long long int i=1; i<=n; i++){
        for(long long int j=0; j<=sum; j++){
            dp[i][j] = dp[i-1][j];
            if(j>=val[i-1])
                dp[i][j] = min(dp[i][j], dp[i-1][j-val[i-1]] + wt[i-1]);
            if(i==n && dp[i][j]<=Weight)
                ans = max(ans,j);
        }
    }
    return ans;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL); cout.tie(NULL);
    int n, w;
    long long int sum = 0;
    cin>>n>>w;
    vector<long long int> wt(n), val(n);
    for(int i=0;i<n;i++){
        cin>>wt[i]>>val[i];
        sum += val[i];
    }
    cout<<knapsack(wt, val, n, w, sum)<<endl;
    return 0;
}

Measured memory_bytes: 80256
#include<iostream>

using namespace std;

int main(){

    int a, b, c;

    cin >> a;
    cin >> b;
    cin >> c;

    if(a > b){
        a = a + b;
        b = a - b;
        a = a - b;
    }

    if(b > c){
        b = b + c;
        c = b - c;
        b = b - c;
    }

    if(a > b){
        a = a + b;
        b = a - b;
        a = a - b;
    }    

    cout << a << " " << b << " " << c << endl;

    return 0;

}


Measured memory_bytes: 3068
N,C,K = map(int,input().split())
t = [int(input()) for _ in range(N)]
t.sort()
L = 0
R = N-1
answer = 0
nextLeft = True

while L<=R:
    answer += 1
    if nextLeft:
        # print(L,R)
        nextLeft = False
        TLeft = t[L]
        count = 1
        L += 1
        while count < C:
            if L == N:
                break
            if t[L] <= TLeft + K:
                count += 1
                L+=1
            else:
                break
    else:
        # print(L,R)
        nextLeft = True
        TRight = t[R]
        count = 1
        R -= 1
        while count < C:
            if R == -1:
               break 
            if t[R] >= TRight - K:
                count += 1
                R -= 1
            else:
                break
print(answer)



Measured memory_bytes: 7508
import java.io.File;
import java.io.FileInputStream;
import java.util.Scanner;
import java.util.Map.Entry;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.PriorityQueue;

public class Main {
	
	public static void main(String[] args) throws IOException {
		FastScanner sc = new FastScanner(System.in);
		
		String S = sc.next();
		String p = "CODEFESTIVAL2016";
		int ans = 0;
		for(int i = 0; i < S.length(); i++)
			if(S.charAt(i) != p.charAt(i)) ans++;
		System.out.println(ans);
	}
}

class FastScanner {
    private InputStream in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    public FastScanner(InputStream in) {
		this.in = in;
	}
    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }else{
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }
    private int readByte() {
    	if (hasNextByte()) return buffer[ptr++];
    	else return -1;
    }
    private static boolean isPrintableChar(int c){
    	return 33 <= c && c <= 126;
    }
    public boolean hasNext() {
    	while(hasNextByte() && !isPrintableChar(buffer[ptr]))
    		ptr++; return hasNextByte();
    }
    public String next() {
        if (!hasNext()) throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while(isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    public long nextLong() {
        if (!hasNext()) throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while(true){
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            }else if(b == -1 || !isPrintableChar(b)){
                return minus ? -n : n;
            }else{
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }
    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
        return (int) nl;
    }
    public double nextDouble() {
    	return Double.parseDouble(next());
    }
}

Measured memory_bytes: 24660
from collections import Counter


def check(N, A):
    d = max(A)
    if d >= N:
        return False
    c = Counter(A)
    cnt = 0
    if d % 2 == 0:
        if c[d//2] != 1:
            return False
        cnt += 1
        mn = d//2+1
    else:
        if c[d//2+1] != 2:
            return False
        cnt += 2
        mn = d//2+2
    for i in range(mn, d+1):
        if c[i] < 2:
            return False
        cnt += c[i]
    return cnt == N


def main():
    N = int(input())
    A = list(map(int, input().split()))
    if check(N, A):
        print("Possible")
    else:
        print("Impossible")


if __name__ == "__main__":
    main()


Measured memory_bytes: 38384
import java.util.*;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long A = Long.parseLong(sc.next());
		long B = Long.parseLong(sc.next());
		if (gcd(A, B)==1) {
			System.out.println(1);
		} else {
			System.out.println(factorization(gcd(A, B)).size()+1);
		}
	}
	static long gcd(long a,long b) {
	    long temp;
	    while ((temp=a%b)!=0) {
	        a=b;
	        b=temp;
	    }
	    return b;
	}
	static ArrayList<long[]> factorization (long n) {
	    ArrayList<long[]> list = new ArrayList<long[]>();
	    long tmp= n ;
	    for (int i=2;i<=Math.sqrt(n);i++) {
	        if (tmp%i==0) {
	            int cnt=0;
	            while (tmp%i==0) {
	                cnt++;
	                tmp/=i;
	            }
	            long[] x = {i, cnt};
	            list.add(x);
	        }
	    }
	    if (tmp!=1) {
	        long[] x = {tmp, 1};
	        list.add(x);
	    }

	    if (list.size()==0) {
	        long[] x = {n, 1};
	        list.add(x);
	    }
	    return list;
	}
}

Measured memory_bytes: 23124
#include<bits/stdc++.h>
using namespace std;
int main() {
	long long n = 0, d = 0, count = 0, x = 0, y = 0;
	scanf("%lld %lld", &n, &d);
	for(int i = 0; i < n; i++)
	{
		scanf("%lld %lld", &x ,&y);
		if(x * x + y * y <= d * d)
			count++;
	}
	printf("%lld", count);
	return 0;
}


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

#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define repr(i,n) for(int i=(int)(n-1);i>=0;i--)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb(s) push_back(s)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout << #x"=" << x <<endl
#define maxch(x,y) x=max(x,y)
#define minch(x,y) x=min(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt(x) bitset<32>(x).count()

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<P, int> PPI;
typedef pair<int, P> PIP;
typedef pair<ll, ll> PL;
typedef pair<P, ll> PPL;
typedef set<int> S;

#define INF INT_MAX/3

#define MAX_N 1000000001

int main(){
	cin.sync_with_stdio(false);
	int n;
	cin >> n;

	cout << n*(n+1)/2 << endl;

	return 0;
}

Measured memory_bytes: 256
n = int(input())
result = {'AC':0, 'WA':0, 'TLE':0, 'RE':0}
for i in range(n):
  s = input()
  result[s] += 1
print('AC x',result['AC'])
print('WA x',result['WA'])
print('TLE x',result['TLE'])
print('RE x',result['RE'])

Measured memory_bytes: 9144
import sys
sys.setrecursionlimit(1000000)

n = int(input())
tree = [[] for i in range(n)]
for i in range(n - 1):
    j = int(input())
    j -= 1
    i += 1
    tree[i].append(j)
    tree[j].append(i)

def dfs(pos):
    if pos != 0 and len(tree[pos]) == 1:
        return 1
    li = []
    for next_pos in tree[pos]:
        if visited[next_pos]:
            continue
        visited[next_pos] = True
        li.append(dfs(next_pos))
    li = sorted(li)
    res = 0
    for i in range(len(li)):
        if li[i] > res:
            res = li[i]
        elif li[i] <= res:
            res += 1
    return res + 1

visited = [False] * n
visited[0] = True
print(dfs(0) - 1)


Measured memory_bytes: 122928
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <numeric>
#include <string>

using namespace std;

int main(void){
    string S;
    cin>>S;

    int count0=0;
    int count1=0;

    for(int i=0;i<S.length();i++){
        if(S[i]=='0'){
            count0++;
        }
        else if (S[i]=='1')
        {
            count1++;
        }        
    }

    int ans = count0<count1? count0 : count1;
    ans*=2;

    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 512
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353

n, m, k = LI()


fac = [1] * (n + 1)
inv = [1] * (n + 1)
for j in range(1, n + 1):
    fac[j] = fac[j-1] * j % mod

inv[n] = pow(fac[n], mod-2, mod)
for j in range(n-1, -1, -1):
    inv[j] = inv[j+1] * (j+1) % mod


def comb(n, r):
    if r > n or n < 0 or r < 0:
        return 0
    return fac[n] * inv[n - r] * inv[r] % mod

ret = 0
for i in range(k + 1):
    j = n - 1 - i
    ret += m * pow(m - 1, j, mod) * comb(n - 1, j) % mod

print(ret % mod)









Measured memory_bytes: 84008
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

a,b = [int(i) for i in readline().split()]


ans = []
for i in range(b-a+1,b+a):
    ans.append(i)

print(*ans)



Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define REP(i, n, s) for (int i = (s); i < (n); i++)
#define PI 3.141592653589793
#define EPS 1e-15
#define SIZE 200001
using namespace std;
typedef long long int LL;
typedef long double LD;

int N;
LL K;
double s[SIZE];

int count(int i, double X) {
	if (i == N - 1) return 0;
	int all = (N - i) / 2;
	int l = 0, r = all + 1;
	while(r - l > 1) {
		int m = (l + r) / 2;
		double area = (s[i] + s[m] + s[N - i - m]) / 2.0;
		if (area > X + EPS) r = m;
		else l = m;
	}
	if (r == all + 1) return N - i - 1;
	return l * 2;
}

bool check(double X) {
	LL sum = 0;
	REP(i, N, 1) {
		sum += count(i, X);
	}
	return sum*(LL)N >= K;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> K;
	REP(i, N+1, 0) {
		s[i] = sin(2.0*PI*(double)i/(double)N);
	}
	K = 3LL * K;
	double l = 0.0, r = 2.0 * PI;
	REP(i, 50, 0) {
		double m = (l + r) / 2;
		if (check(m)) r = m;
		else l = m;
	}
	cout << fixed << setprecision(20) << r << endl;
	return 0;
}

Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using pll = pair<ll, ll>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(i) begin(i), end(i)

const int INF = 0x3fffffff;
const ll MINF = 0x7fffffffffff;
const ld DINF = numeric_limits<ld>::infinity();
const int MOD = 1000000007;
const int MODD = 998244353;
const ld EPS = 1e-9;
const ld PI = 3.1415926535897932;

template<class T> bool chmin(T &a, const T &b){ if(a > b){ a = b; return 1; } else return 0; }
template<class T> bool chmax(T &a, const T &b){ if(a < b){ a = b; return 1; } else return 0; }
template<class T> auto min(const T& a){ return *min_element(all(a)); }
template<class T> auto max(const T& a){ return *max_element(all(a)); }

ll gcd(ll a, ll b){ while(b){ ll c = b; b = a % b; a = c; } return a; }
ll lcm(ll a, ll b){ if(!a || !b) return 0; return a * b / gcd(a, b); }
ll pow_mod(ll n,ll k,ll m){ll r = 1;for(; k > 0;k >>= 1) {if (k & 1) r = (r * n) % m; n = (n * n) % m;}return r;}

//ここから。
int main(){
    ll D,T,S;
    cin >> D >> T >> S;
    if(S * T >= D) cout << "Yes" << endl;
    else cout << "No" << endl;
}

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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,n,m) for(int i=(int)(n); i<=(int)(m); i++)
#define RFOR(i,n,m) for(int i=(int)(n); i>=(int)(m); i--)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

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

#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define ins insert

using namespace std;

/* Some Libraries */

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

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n,a,b; cin>>n>>a>>b;
    ll sum = a+b;
    cout<<(n/sum*a)+min(n%sum,a)<<endl;
    return 0;
}


Measured memory_bytes: 384
def main():
    from collections import defaultdict
    from heapq import heappush, heappop
    _, m, *ab = map(int, open(0).read().split())
    works = defaultdict(list)
    # == zip(ab[0::2], ab[1::2])
    for a, b in zip(*[iter(ab)]*2):
        # 最大値が欲しいが、heappopは最小値を取り出すので-1倍しておく
        works[a].append(-b)

    candidates, pay = [], []
    for day in range(1, m+1):
        for x in works[day]:
            heappush(candidates, x)
        if candidates:
            pay.append(heappop(candidates))
    print(-sum(pay))


if __name__ == "__main__":
    main()


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

#define REP(i,n) for(int i=0;i<(n);i++)
#define int long long
#define ALL(x) (x).begin(),(x).end()
typedef pair<int, int> pii;



vector<int>v,v_even;
int dp[1000010],dp_even[1000010];
int calc(int n){
    return n*(n+1)*(n+2)/6;
}

int rec(int n){
    if(n==0)return 0;
    if(dp[n])return dp[n];
    else{
        int res = 1e9;
        for(auto x:v){
            if(x>n)break;
            res=min(res,rec(n-x)+1);
        }
        return dp[n]=res;
    }
}
int rec_even(int n){
    if(n==0)return 0;
    if(dp_even[n])return dp_even[n];
    else{
        int res = 1e9;
        for(auto x:v_even){
            if(x>n)break;
            res=min(res,rec_even(n-x)+1);
        }
        return dp_even[n]=res;
    }

}
void solve() {
    for(int i=1;i<10000;i++){
        int num=calc(i);
        if(calc(i)>=1e6){
            break;
        }
        else{
            v.push_back(num);
            if(num&1)v_even.push_back(num);
        }
    }
    while(true){
        int n;cin>>n;
        if(n==0)exit(0);
        cout<<rec(n)<<" "<<rec_even(n)<<endl;
    }
}

signed main() {
	solve();
}



Measured memory_bytes: 47424
///mAAria...
#include<bits/stdc++.h>
 
using namespace std;
 
#define int long long
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define all(v) v.begin(),v.end()
#define allr(v) v.rbegin(),v.rend()
#define ld long double
#define ff first
#define ss second
#define pb push_back
#define pii pair<int,int>
#define pi 3.1415926535897932384626433832
#define mod 1000000000
//#define mod 998244353
#define inf 1000000000
#define pr1(a) cout << a << "\n"
#define pr2(a,b)cout << a <<  " " <<b<< "\n"
#define pr3(a,b,c) cout << a <<" " << b << " " << c << "\n"

const long double PI = acos(-1);

int powm(int a, int b) {
    int res=1;
    while(b) {
        if(b&1)
            res=(res*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return res;
}

int gcd(int a, int b){
    if(b==0)return a;
    return gcd(b,a%b);
}
const int maxn = 2*1e5 + 10;

int a[maxn];

void solve(){
    int n;
    cin >> n;
    

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

    for(int i = 1;i<=n;i++)cout << a[i] <<endl;
    

} 

signed main() 
{   
    IOS;
    int t = 1;
    // cin >> t;

    for(int i = 1;i<=t;i++){
        solve();
    }
    return 0;
} 

 

Measured memory_bytes: 5104
#include<bits/stdc++.h>
using namespace std ;
	#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	#define lli long long int
	#define ulli unsigned long long int
	#define ff first
	#define ss second
	#define mp make_pair
	#define pb push_back
	#define pf pop_front()
	#define lb lower_bound
	#define ub upper_bound
	#define bs binary_search
	#define loop(i,a,b) for(lli i=a;i<b;i++)
	#define loopi(i,a,b) for(int i=a;i<b;i++)
	#define all(v) v.begin(), v.end()
	#define mod 1000000007
	#define inf 100000000000000000
	#define lld long double
	#define pll pair<long long int,long long int>
	#define pii pair<int,int>
	#define vll vector<lli>
	#define vii vector<int>
	#define endl '\n'
	#define setp(k, x) fixed << setprecision(k) << (x)
	#define deb(x) cerr << #x << ": " << x << " " << endl;
	#define debug(x) cout << "m here-" <<#x<<" ..."<<"\n";
	#define printa(a,n) for(lli i=0;i<n;i++) cout<<a[i]<<" "; cout<<"\n";
  #define printv(a) for(lli i=0;i<a.size();i++) cout<<a[i]<<" "; cout<<"\n";
	bool sortcol( const vector<lli>& v1, const vector<lli>& v2 ) //sort on basis of column //use- sort(vect.begin(), vect.end(),sortcol);
      { return v1[1] < v2[1]; }//[] o based indexing in column
	bool sortpair(const pair<lli, lli> &a, const pair<lli, lli> &b)
			{return a.second < b.second;}
	struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

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


int main ()
{
	// fastio
 	// lli  t;
 	// cin>>t;
 	// while(t--)
 	{
	   double n,i,d,a,b,c=1,j,k;
    cin>>k;
    a=100;
    while(a<k)
      {
        a=a*(pow(1.01,1));
        a=floor(a);
        c++;
      }
      c--;
      cout<<c<<"\n";






 	}
}


Measured memory_bytes: 3784
#include <iostream>
#include <string>

using namespace std;

int main(void){
    int n, k;
    string s;
    cin >> n;
    cin >> s;
    cin >> k;
    for(int i = 0; i < n; ++ i) s[i] = ((s[i] == s[k - 1])? s[i] : '*');
    cout << s << endl;
    
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>
#include <limits.h>
int acs(const void *a, const void *b){return *(int*)a - *(int*)b;} /* 1,2,3,4.. */
int des(const void *a, const void *b){return *(int*)b - *(int*)a;} /* 8,7,6,5.. */
#define min(a,b) (a < b ? a: b)
#define max(a,b) (a > b ? a: b)

#define MAXN (200000)
#define MOD (998244353)

char s[4];
char t[4];

int main(void)
{
    int n;
    
    scanf("%s", s);
    scanf("%s", t);

    int c =0;
    for(int i=0;i<3;i++)
    {
        if(s[i]==t[i]) c++;
    }

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

    return 0;
}







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

int main() {
  string s; cin >> s;
  string ans;
  
  for (int i=0; i<s.size(); i++){
    if (s.at(i) == '0')      ans += "0";
    else if (s.at(i) == '1') ans += "1";
    else if (s.at(i) == 'B'){
      if (ans.size() > 0){
        ans.pop_back();
      }
    }
  }
  
  cout << ans <<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define BIG 1000000010
#define repi(i,x,n) for(int i=x;i<n;i++)
#define rep(i,n) repi(i,0,n)
#define repn(i,n) for(int i=n;i>=0;i--)
typedef long long int ll;

int n,m;
int k;
int A;
vector<int> a[10];
int c[10]={0};
int p[10];
int ans=0;

void solve(int cnt){
  if(cnt==n){
    //cout<<c[0]<<" "<<c[1]<<endl;
    rep(i,m){
      int b=0;
      rep(j,a[i].size()){
	b+=c[a[i][j]-1];
      }
      if(b%2!=p[i]) break;
      else if(i==m-1) ans++;
    }
  }
  else{
    c[cnt]=0;
    solve(cnt+1);
    c[cnt]=1;
    solve(cnt+1);
  }
}


int main(){
  cin>>n>>m;
  rep(i,m){
    cin>>k;
    rep(j,k){
      cin>>A;
      a[i].push_back(A);
    }
  }
  rep(i,m) cin>>p[i];
  solve(0);
  cout<<ans<<endl;

  return 0;
}






Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
//cin.ignore();	// better to use 2 times getline(cin,s);
// g++ iterator.cpp -std=c++17
//cout << (A + B == C ? "YES" : "NO") << endl;
#define pb push_back
#define mk make_pair
#define vll vector<ll>
#define mll map<ll,ll >
#define mlli map<ll,ll>::iterator
#define size size()
#define endl "\n"
#define ll long long int
#define ld long double
void fast(){
   	ios_base::sync_with_stdio(false);
   	cin.tie(NULL);
   	cout.tie(NULL);}


int main(void)
{
  fast();
  string s;
  cin>>s;
  int cnta=0;
  int cntb=0;
  for(int i=0;i<s.size;i++)
  {
      if(s[i]=='A')
      {
          cnta++;
      }
      else
      {
          cntb++;
      }
  }
  if(cnta>=1 && cntb>=1)
  {
      cout<<"Yes"<<endl;
  }
  else
  {
      cout<<"No"<<endl;
  }
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<deque>
using namespace std;
#define ll long long
const int mod = 1000000007;
const ll INF = 1000000000000000000;

struct UnionFind {
	vector<int> par;
	UnionFind(int x) : par(x, -1) {}
	void init(int x) { par.assign(x, -1); }
	int root(int x) {
		if (par[x] <= -1) return x;
		else return root(par[x]);
	}
	bool issame(int x, int y) {
		return root(x) == root(y);
	}
	bool merge(int x, int y) {
		x = root(x); y = root(y);
		if (x == y) return false;
		if (par[x] > par[y]) swap(x, y);
		par[x] += par[y];
		par[y] = x;
		return true;
	}
	int size(int x) {
		return -par[root(x)];
	}
};
int ans[100010];
vector<int> V[100010];
int main()
{
	int N, M, K;
	cin >> N >> M >> K;
	UnionFind uf(N);
	for (int i = 0; i < M; i++) {
		int A, B;
		cin >> A >> B;
		A--; B--;
		V[A].push_back(B);
		V[B].push_back(A);
		uf.merge(A, B);
	}
	for (int i = 0; i < N; i++) {
		ans[i] = uf.size(i) - V[i].size() - 1;
	}
	for (int i = 0; i < K; i++) {
		int C, D;
		cin >> C >> D;
		C--; D--;
		if (uf.issame(C, D)) {
			ans[C]--;
			ans[D]--;
		}
	}
	for (int i = 0; i < N; i++) {
		cout << ans[i] << " ";
	}
	cout << endl;
}

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

int main() {
	int n, k;
	cin >> n >> k;
	set<int>a = { 0,1,2,3,4,5,6,7,8,9 };
	for (int i = 0; i < k; i++) {
		int x;
		cin >> x;
		a.erase(x);
	}
	while (true) {
		bool exist = true;
		int y = n;
		while (y>0) {
			if (!a.count(y % 10)) {
				exist = false;
				break;
			}
			else y = y / 10;
		}
		if (exist)break;
		else n++;
	}
	cout << n << endl;
}


Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<queue>
#define manx 150005
using namespace std;
int a[200005];
int main()
{
    int n,mm=-999999999;
    int i,j,sum;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    int maxa=-2000000000,mina=a[0];
    for(i=1;i<n;i++)
    {
        maxa=max(maxa,a[i]-mina);
        mina=min(mina,a[i]);
    }
    cout<<maxa<<endl;
    return 0;
}



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

const int MAX = 2e5 + 5;
char a[MAX];

int main() {
	scanf("%s", a + 1);

	int n = strlen(a + 1);

	int x = -1, y = -1;
	for(int i = 1; i <= n; i++) {
		if(i + 1 <= n && a[i] == a[i + 1])
			x = i, y = i + 1;

		if(i + 2 <= n && a[i] == a[i + 2])
			x = i, y = i + 2;
	}

	printf("%d %d\n", x, y);
	return 0;
}

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

namespace AOJ_ICPC1 {

	class Program {
		static void Main(string[] args) {
			while (true) {
				string[] strs = Console.ReadLine().Split(' ');
				int N = int.Parse(strs[0]);
				int A = int.Parse(strs[1]);
				int B = int.Parse(strs[2]); 
				int C = int.Parse(strs[3]); 
				int X = int.Parse(strs[4]);
				
				if (N==0) break;
				int[] Y = new int[N];
				string[] strsy = Console.ReadLine().Split(' ');
				for (int n = 0; n < N; n++) Y[n] = int.Parse(strsy[n]);

				Console.WriteLine(result(A, B, C, X, Y));
			}
		}
		static int result(int A, int B, int C, int X, int[] Y) {
			int flame = 0;
			Func<int, int> nextFlame = (x) => {
				flame++;
				return (A * x + B) % C;
			};
			for (int n = 0; n < Y.Length; n++) {
				while (X != Y[n]) {
					if (flame >= 10000) return -1;
					X = nextFlame(X);
				}
				X = nextFlame(X);
			}
			return flame-1;
		}
	}
}

Measured memory_bytes: 5944
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		String dream = "dream";
		String dreamer = "dreamer";
		String erase = "erase";
		String eraser = "eraser";
		String dreamerase = "dreamerase";
		String dreameraser = "dreameraser";

		Scanner scan = new Scanner(System.in);
		String s = scan.next();
		scan.close();

		StringBuilder t = new StringBuilder(s);

		boolean yes = true;

		while(true) {
			int indexDream =  t.indexOf(dream);
			int indexDreamer = t.indexOf(dreamer);
			int indexErase = t.indexOf(erase);
			int indexEraser = t.indexOf(eraser);
			int indexDreamErase = t.indexOf(dreamerase);
			int indexDreamEraser = t.indexOf(dreameraser);

			if(indexDreamEraser == 0) {
				t.delete(0, dreameraser.length());
			} else if(indexDreamErase == 0) {
				t.delete(0, dreamerase.length());
			} else if(indexDreamer == 0){
				t.delete(0, dreamer.length());
			} else if(indexDream == 0) {
				t.delete(0, dream.length());
			} else if(indexEraser == 0) {
				t.delete(0, eraser.length());
			} else if(indexErase == 0) {
				t.delete(0, erase.length());
			} else {
				yes = false;
				break;
			}

			if(t.length() == 0) {
				break;
			}
		}

		if(yes == true) {
			System.out.println("YES");
		} else {
			System.out.println("NO");
		}

	}

}


Measured memory_bytes: 26904
#include <bits/stdc++.h>
#define ALL(a)  (a).begin(),(a).end()
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
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; }
const long long INF = 1LL << 60;

vector<vector<ll>> dp(110000, vector<ll>(3, 0));

int main(){
  int N;
  cin >> N;
  vector<vector<ll>> a(N, vector<ll>(3));
  for(int i = 0; i < N; i++){
    cin >> a.at(i).at(0) >> a.at(i).at(1) >> a.at(i).at(2);
  }

  dp.at(0) = {a.at(0).at(0), a.at(0).at(1), a.at(0).at(2)};

  for(int i = 1; i < N; i++){
    for(int j = 0; j < 3; j++){
      for(int k = 0; k < 3; k++){
        if(j == k) continue;
        chmax(dp.at(i).at(j), dp.at(i-1).at(k) + a.at(i).at(j));
      }
    }
  }
  cout << max(dp.at(N-1).at(0), max(dp.at(N-1).at(1), dp.at(N-1).at(2))) << endl;
}


Measured memory_bytes: 11776