akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<(n); ++i)
#define rep1(i,n) for(int i=1; i<=(n); ++i)
#define repi(i,a,b) for(int i=a; i<=(b); ++i)
#define rrep(i,n) for(int i=(n-1); i>=0; --i)
#define ALL(obj) (obj).begin(), (obj).end()
#define RALL(obj) (obj).rbegin(), (obj).rend()
#define pb push_back
#define mp make_pair
#define to_s to_string
#define sz(v) (int)v.size()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() )
#define pr(x) cout<<(x)<<'\n'
#define debug(x) cout << #x << ": " << (x) << '\n'
#define yes "Yes"
#define no "No"
using namespace std;
using ll = long long;
using Edge = pair<int,long long>;
using Graph = vector<vector<Edge>>;
typedef pair<int,int> P;
struct aaa{aaa(){ cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20);};}aaaaaaa;
int MOD = 1e9 + 7;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return (a*b)/gcd(a,b);}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};


int main(){
    int R,G;
    cin >> R >> G;
    pr(2*G-R);
}

Measured memory_bytes: 256
#include <stdio.h>

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int bubbleSort(int A[],int N) {
    int i,j;
    int sw = 0;
    unsigned short flag = 1;
    for(i=0;flag;i++) {
        flag = 0;
        for(j=N-1;j>=i+1;j--) {
            if(A[j]<A[j-1]) {
                swap(&A[j],&A[j-1]);
                flag = 1;
                sw++;
            }
        }
    }
    return sw;
}

int main(void) {
    int i, A[100], N, sw;
    scanf("%d",&N);
    for(i=0;i<N;i++) scanf("%d",&A[i]);

    sw = bubbleSort(A,N);

    for(i=0;i<N;i++) {
        if (i) printf(" ");
        printf("%d",A[i]);
    }
    printf("\n%d\n",sw);

    return 0;
}


Measured memory_bytes: 2144
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define rep(i,n) for(ll i=0;i<(n);i++)
#define pll pair<ll,ll>
#define pq priority_queue
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define lb(c,x) distance(c.begin(),lower_bound(all(c),x))
#define ub(c,x) distance(c.begin(),upper_bound(all(c),x))

using namespace std;

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 ll mod=1e9+7;

int main(){
    string s;
    cin >> s;
    ll n=s.length();
    vector<vector<ll>> dp(n+1,vector<ll>(4));
    dp[0][0]=1;
    rep(i,n){
        if(s[i]=='?'){
            rep(k,3){
                rep(j,4){
                    dp[i+1][j]+=dp[i][j];
                    dp[i+1][j]%=mod;
                }
                dp[i+1][k+1]+=dp[i][k];
                dp[i+1][k+1]%=mod;
            }
        }
        if(s[i]=='A'){
            rep(j,4){
                dp[i+1][j]+=dp[i][j];
                dp[i+1][j]%=mod;
            }
            dp[i+1][1]+=dp[i][0];
            dp[i+1][1]%=mod;
        }
        if(s[i]=='B'){
            rep(j,4){
                dp[i+1][j]+=dp[i][j];
                dp[i+1][j]%=mod;
            }
            dp[i+1][2]+=dp[i][1];
            dp[i+1][2]%=mod;
        }
        if(s[i]=='C'){
            rep(j,4){
                dp[i+1][j]+=dp[i][j];
                dp[i+1][j]%=mod;
            }
            dp[i+1][3]+=dp[i][2];
            dp[i+1][3]%=mod;
        }
    }
    cout << dp[n][3] << endl;
    return 0;
} 

Measured memory_bytes: 7424
a,b = map(int, input().split())
s = input()
d = 0

for i in list(s):
    if i == '-':
        d += 1

try:
    map(int, s.split('-'))
    if len(s) == a + b + 1 and s[a] == '-' and d < 2:
        print('Yes')
    else:
        print('No')
except:
    print('No')

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

#define MAX 24*60*60

int main(){

  int train[MAX];
  int N;

  while(1){

    cin >> N;
    if(N == 0) break;
    int ans = 0;
    for(int i = 0 ; i < MAX ; i++){
      train[i] = 0;
    }    

    int h1,m1,s1,h2,m2,s2;
    char tmp;

    for(int i = 0; i < N ; i++){
    
      cin  >> h1 >> tmp >> m1 >> tmp >> s1 >> h2 >> tmp >> m2 >> tmp >> s2;
      //  cout << h1 << " " << m1 << " " << s1 << " " << h2 << " " << m2 << " " << s2 << endl;
      // cout   << train[3*60*60 +1] << " " << train[3*60*60] << endl;


      //列車を増やすとき

      bool OK = true;
      for(int i =  s1 + 60*m1 + 60*60*h1 ; i <= s2+(60*m2)+(60*60*h2)-1 ;i++){
	if(train[i] == 0){
	  OK = false;
	  break;
	}
      }  
      
      if(OK == false){
	ans++;
	for(int i = 0 ; i < s1 + 60*m1 + 60*60*h1 ;i++){
	  train[i]++;
	} 
	for(int i = s2 + 60*m2 + 60*60*h2 ; i < MAX ;i++){
	  train[i]++;
	} 
      } 
      //足りているとき
      else{
	for(int i =  s1 + 60*m1 + 60*60*h1 ; i <= s2+(60*m2)+(60*60*h2)-1 ;i++){
	  if(train[i] != 0) train[i]--;
	} 
      }
      //   cout << train[0] <<" "<< train[MAX-1] << endl;
    }
    cout << ans << endl;
  }  
  return 0;
}

Measured memory_bytes: 1496
n = int(input())
v = list(map(int,input().split()))
l1 = []
l2 = []
for i,v_ in enumerate(v):
    if i%2==0:
        l1.append(v_)
    else:
        l2.append(v_)

from collections import Counter
if len(set(v))==1:
    print(n//2)
else:
    c1 = Counter(l1).most_common(2)
    c2 = Counter(l2).most_common(2)
    if c1[0][0]==c2[0][0]:
        print(n-max(c1[0][1]+c2[1][1], c1[1][1]+c2[0][1]))
    else:
        print(n-c1[0][1]-c2[0][1])

Measured memory_bytes: 16612
#include<bits/stdc++.h>
#define N 100100
#define M 200100
using namespace std;
int d[N];
int id[N];
int c[N];
int ex[M],ey[M],ans[M];
char col[N];
vector<int> g[N];
bool cmp(int i,int j){
	return d[i]<d[j];
}
int main(){
	int n,m;
	bool fail=false;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&d[i]);
	for(int i=0;i<m;i++){
		scanf("%d%d",&ex[i],&ey[i]);
		g[ex[i]].push_back(i);
		g[ey[i]].push_back(i);
	}
	for(int i=0;i<n;i++) id[i]=i+1;
	sort(id,id+n,cmp);
	for(int i=0;i<n;i++){
		int u=id[i];
		fail=true;
		for(int j=0;j<g[u].size();j++){
			int t=g[u][j];
			int v=ex[t]^ey[t]^u;
			if(d[v]<=d[u]){
				fail=false;
				ans[t]=d[u];
				if(!col[u]){
					if(col[v]=='B') col[u]='W';
					else if(col[v]=='W') col[u]='B';
					else{
						col[u]='B';
						col[v]='W';
					}
				}					
			}
		}
		if(fail) break;
	}
	if(fail) puts("-1");
	else{
		puts(col+1);
		for(int i=0;i<m;i++) printf("%d\n",ans[i]);
	}
	return 0;
}

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

int N;
long long x;
int main() {
    while (cin >> N >> x) {
        vector<long long> a(N);
        for (int i = 0; i < N; ++i) cin >> a[i];
        sort(a.begin(), a.end());
        int res = 0;
        for (int i = 0; i < N; ++i) {
            if (x >= a[i]) ++res, x -= a[i];
            else break;
        }
        if (x) res = min(res, N-1);
        cout << res << endl;
    }
}


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

using namespace std;

int main() {
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  string s;
  cin >> s;
  cout << (s == "ABC" ? "ARC" : "ABC") << "\n";
  return 0;
}


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

int main() {
  int N, K;
  cin >> N >> K;
  vector<uint64_t> H(N);
  for (int i=0; i<N; i++) cin >> H.at(i);

  if (K >= N) {
    cout << 0 << endl;
    return 0;
  }
  
  if (K == 0) {
    cout << accumulate(H.begin(), H.end(), 0LL) << endl;
    return 0;
  }

  sort(H.begin(), H.end());
  reverse(H.begin(), H.end());

  ll ans=0;
  for (int i=0; i<N-K; i++) {
    ans += H.at(K+i);
  }
  cout << ans << endl;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,s,n) for(int i = (s); i < (n); i++)
#define all(v) v.begin(), v.end()

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  ll n, m;
  cin >> n >> m;
  
  ll mini = 0;
  ll maxi = 1e5 +1;
  
  rep(i, 0, m) {
    ll l, r;
    cin >> l >> r;
    if(l > mini) mini = l;
    if(r < maxi) maxi = r;
  }  
  cout << max(ll(0), maxi -mini +1) << "\n";
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <map>
#include <cmath>
#include <functional>
using namespace std;

long long N, K, A[1 << 18], V1[50], V2[50], dp[50][2], ret = 0;

int main() {
	cin >> N >> K;
	for (int i = 0; i < N; i++) cin >> A[i];

	for (int i = 40; i >= 0; i--) {
		long long S1 = 0, S2 = 0;
		for (int j = 0; j < N; j++) {
			if ((A[j] / (1LL << i)) % 2 == 0) S1 += (1LL << i);
			else S2 += (1LL << i);
		}
		V1[i] = S2; V2[i] = S1;
	}
	for (int i = 41; i >= 0; i--) { dp[i][0] = -(1LL << 60); dp[i][1] = -(1LL << 60); }
	
	dp[41][0] = 0;
	for (int i = 40; i >= 0; i--) {
		if (dp[i + 1][0] != -(1LL << 60)) {
			if ((K / (1LL << i)) % 2 == 1) {
				dp[i][1] = max(dp[i][1], dp[i + 1][0] + V1[i]);
				dp[i][0] = max(dp[i][0], dp[i + 1][0] + V2[i]);
			}
			else {
				dp[i][0] = max(dp[i][0], dp[i + 1][0] + V1[i]);
			}
		}
		if (dp[i + 1][1] != -(1LL << 60)) {
			dp[i][1] = max(dp[i][1], dp[i + 1][1] + V1[i]);
			dp[i][1] = max(dp[i][1], dp[i + 1][1] + V2[i]);
		}
	}
	cout << max(dp[0][0], dp[0][1]) << endl;
	return 0;
}

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

int main()
{
    int W, H, x, y, r;
    cin >> W >> H >> x >> y >> r;

    if (r <= x && x <= W - r && r <= y && y <= H - r) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}



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

namespace CSharpSample01
{
    
    class Program
    {
    
        static void Main(string[] args)
        {
            string[] input = Console.ReadLine().Split(' ');
            double W = double.Parse(input[0]);
            double H = double.Parse(input[1]);
            double x = double.Parse(input[2]);
            double y = double.Parse(input[3]);

            double area = W * H / 2; ;
            int type = 0;

            if(x == W / 2 || y == H / 2)
            {               

                if(x == W / 2 && y == H / 2)
                {
                    type = 1;
                }
                else
                {
                    type = 0;
                }
            }
            else
            {
                type = 0;              
                
            }

            Console.WriteLine($"{area:f12} {type}");
            
        }
    }
}

Measured memory_bytes: 11220
package main

import "fmt"

func main() {
	var A, B, C int
	fmt.Scan(&A, &B, &C)

	flag := false
	for i := A; i <= B*A; i += A {
		if i%B == C {
			flag = true
		}
	}

	if flag {
		fmt.Println("YES")
	} else {
		fmt.Println("NO")
	}
}


Measured memory_bytes: 512
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <iomanip> // setprecision
#include <complex> // complex
#include <math.h> 
#include <climits> 
#include <assert.h>
#include <random>
#define rep(i,n) for(int i=0; i<(n); i++)
using namespace std;
using ll = long long;
using P = pair<int,int>;
constexpr ll INF = 1e18;
constexpr int inf = 1e9;
constexpr ll mod2 = 1'000'000'007;
constexpr ll mod = 998244353;
const double PI = 3.14159265358;
const int dx[8] = {1, 0, -1, 0,1,1,-1,-1};
const int dy[8] = {0, 1, 0, -1,1,-1,1,-1};
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
// ---------------------------------------------------------------------------


vector<vector<int>> G;
vector<int> A;
vector<bool> dist;
int mn,id;

void dfs(int v){
  if(chmin(mn,A[v])) id = v;
  dist[v] = true;
  for(int nv: G[v]){
    if(dist[nv]) continue;
    dfs(nv);
  }
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int N,M;
  cin >> N >> M;
  A.resize(N);
  for(int i=0; i<N; i++) cin >> A[i];
  G.resize(N);
  for(int i=0; i<M; i++){
    int a,b;
    cin >> a >> b;
    G[a].emplace_back(b);
    G[b].emplace_back(a);
  }
  if(2*(N-M)-2 > N){
    cout << "Impossible\n";
    return 0;
  }
  if(M == N-1){
    cout << 0 << "\n";
    return 0;
  }
  dist = vector<bool>(N,false);
  ll ans = 0;
  vector<bool> used(N,false);
  for(int i=0; i<N; i++){
    mn = inf;
    if(dist[i]) continue;
    dfs(i);
    ans += mn;
    used[id] = true;
  }
  priority_queue<int,vector<int>,greater<int>> que;
  for(int i=0; i<N; i++){
    if(!used[i]) que.emplace(A[i]);
  }
  for(int i=0; i<(N-M)-2; i++){
    ans += que.top();
    que.pop();
  }
  cout << ans << "\n";
  return 0;
}

Measured memory_bytes: 9772
#include <bits/stdc++.h>
using namespace std;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ll long long
#define all(a) (a).begin(),(a).end()
#define mk make_pair
ll MOD=1000000007;
ll mod=998244353;
int inf=1000001000;
ll INF=10000000000000000;

int main(){
    ll n;
    cin >> n;
    vector<ll> a(n),d(n,0);
    rep(i,n) cin >> a[i];
    ll u=0;
    rep(i,n){
        if (i==0) u+=a[i];
        else{
            d[i]=d[i-1];
            if (u==0){
                d[i]++;
                u+=2;
            }
            u+=a[i]-a[i-1]-2;
        }
    }
    ll ans=1;
    rep(i,n){
        (ans*=n-i-d[n-1-i])%=MOD;
    }
    cout << ans << endl;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
#define N 100000
typedef long long ll;
#define ALL(v) (v).begin(),(v).end()
#define SZ(x) int(x.size())
#define OUT(a) cout<<(a)<<endl
#define VECIN(type, c, n) vector<type> c(n);for(auto& i:c) cin>>i;
    
int main(){
	int n,m;
    cin>>n>>m;
    vector<pair<int,int>> s(n);
    REP(i,n){
        cin>>s.at(i).first>>s.at(i).second;
    }
    sort(ALL(s));
    int k=0;
    priority_queue<int> Q;
    ll ans=0;
    for(int i=1;i<=m;i++){
        while ((k<n)&&(i>=s.at(k).first)){
            Q.push(s.at(k).second);
            k++;
        }
        Q.push(0);
        ans+=Q.top();
        Q.pop();
    }
    OUT(ans);
	return 0;
}

Measured memory_bytes: 1660
import java.util.Scanner;

public class Main {
  public static void main(String args[]) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int x = sc.nextInt();
    int min = 10000;
    for (int i = 0; i < n; ++i) {
      int m = sc.nextInt();
      x -= m;
      min = Math.min(min, m);
    }

    int ans = n + (x / min);

    System.out.println(ans);
    
    sc.close(); 
  }
}


Measured memory_bytes: 21972
#include <bits/stdc++.h>
using namespace std;
#define M 300010
#define LL long long
#define rep(i, x, y) for(int i = (x); i <= (y); ++ i)
inline int read() {
	char ch = getchar(); int x = 0, f = 1;
	while(ch < '0' || ch > '9') {
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while('0' <= ch && ch <= '9') {
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return x * f;
}
int a[M];
vector<int> res;
int main() {
	//freopen("in.txt", "r", stdin);
	int n = read(), A = read(), B = read();
	int now = n;
/*	if(n > A * B || A + B - 1 > n) {
		return puts("-1"), 0;
	}*/
	a[1] = A; n -= A;
	rep(i, 2, B) a[i] = 1, -- n;
	if(n < 0) return puts("-1"), 0;
	rep(i, 2, B) {
		if(n >= A - 1) {
			a[i] += A - 1;
			n -= A - 1;
			continue;
		}
		a[i] += n;
		n = 0;
		break;
	}
	if(n > 0) return puts("-1"), 0;
	rep(i, 1, B) {
		rep(j, now - a[i] + 1, now) {
			res.push_back(j);
		}
		now -= a[i];
	}
	for(int i = 0; i < res.size(); ++ i) {
		printf("%d ", res[i]);
	}
	return 0;
}


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

int main(int argc, char const *argv[])
{
	int h,w;
	cin>>h>>w;
	int a[h][w];
	for (int i = 0; i < h; ++i)
	{
		for (int j = 0; j < w; ++j)
		{
			cin>>a[i][j];
		}
	}
	vector<pair<int,int>> ans1,ans2;
	for (int i = 0; i < h; ++i)
	{
		for (int j = 0; j < w; ++j)
		{
			if (a[i][j]%2==1)
			{
				if (j==w-1)
				{
					if (i==h-1)
					{
						continue;
					}
					else
					{
						ans1.push_back(make_pair(i+1,j+1));
						ans2.push_back(make_pair(i+2,j+1));
						--a[i][j];
						++a[i+1][j];
					}
				}
				else
				{
					ans1.push_back(make_pair(i+1,j+1));
					ans2.push_back(make_pair(i+1,j+2));
					--a[i][j];
					++a[i][j+1];
				}
			}
		}
	}
	cout<<ans1.size()<<endl;
	for (int i = 0; i < ans1.size(); ++i)
	{
		cout<<ans1[i].first<<" "<<ans1[i].second<<" "<<ans2[i].first<<" "<<ans2[i].second<<endl;
	}
	return 0;
}


Measured memory_bytes: 5228
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
using namespace std;


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

    cout << N - i + 1 << endl;

    
}

Measured memory_bytes: 3572
#include<iostream>
#include<queue>
using namespace std;
int N;
int A[1000][1000],id[1000];
int T[1000][1000];
int used[1000];
main()
{
	cin>>N;
	for(int i=0;i<N;i++)
	{
		for(int j=0;j<N-1;j++)
		{
			cin>>A[i][j];
			A[i][j]--;
			T[i][A[i][j]]=j;
		}
	}
	queue<pair<int,int> >P;
	for(int i=0;i<N;i++)
	{
		if(i<A[i][0]&&T[A[i][0]][i]==0)P.push(make_pair(i,A[i][0]));
	}
	int day=1;
	for(;!P.empty();day++)
	{
		queue<pair<int,int> >Q;
		while(!P.empty())
		{
			int u=P.front().first,v=P.front().second;
			P.pop();
			id[u]++;
			if(id[u]<N-1)
			{
				if(T[A[u][id[u]]][u]==id[A[u][id[u]]])
				{
					Q.push(make_pair(u,A[u][id[u]]));
				}
			}
			id[v]++;
			if(id[v]<N-1)
			{
				if(T[A[v][id[v]]][v]==id[A[v][id[v]]])
				{
					Q.push(make_pair(v,A[v][id[v]]));
				}
			}
		}
		P=Q;
	}
	for(int i=0;i<N;i++)if(id[i]<N-1)
	{
		cout<<-1<<endl;
		return 0;
	}
	cout<<day-1<<endl;
}


Measured memory_bytes: 8064
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;

const int N = 100010;
const int mod = 1e9 + 7;

inline int read() {
	int jg = 0, jk = getchar() - '0', f = 1;
	while(jk < 0 || jk > 9) {
		if(jk == '-' - '0')  f = -1; 
		jk = getchar() - '0';
	} 
	while(jk >= 0 && jk <= 9)
		jg *= 10, jg += jk, jk = getchar() - '0';
	return jg * f;
}

ll fac[N], inv[N], c[N], ans, sum[N];
int n, k, a[N];

ll qp(ll x, int y) {
	ll ret = 1;
	while(y) {
		if(y & 1)  ret = ret * x % mod;
		x = x * x % mod, y >>= 1;
	}
	return ret;
}

int main() {
	//freopen("a.txt", "r", stdin);
	n = read(), k = read();
	fac[0] = 1;
	for(int i = 1; i <= n; ++i) {
		a[i] = read();
		fac[i] = fac[i - 1] * i % mod;
	}
	sort(a + 1, a + n + 1);
	for(int i = 1; i <= n; ++i)
		sum[i] = (sum[i - 1] + a[i] + mod) % mod;
	if(k == 1)	{
		printf("0");
		return 0;
	}
	inv[n] = qp(fac[n], mod - 2); 
	k -= 2;
	for(int i = n; i >= 1; --i)
		inv[i - 1] = inv[i] * i % mod;
	for(int i = k; i <= n; ++i)
		c[i] = (fac[i] * inv[k] % mod) * inv[i - k] % mod;
	for(int i = k; i <= n - 2; ++i)
		ans = (ans + (c[i] * ((- sum[n - i - 1] + sum[n] - sum[i + 1] + 2 * mod) % mod) % mod)) % mod;
	printf("%lld", ans);
	return 0;
}

Measured memory_bytes: 3328
import java.util.*;

class Main {
    final Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        new Main().run();
    }

    private void run() {
        int n = sc.nextInt();
        int k = sc.nextInt();

        int[] count = new int[n+1];
        for (int i = 0; i < k; i++) {
            int d = sc.nextInt();
            for (int j = 0; j < d; j++) {
                count[sc.nextInt()]++;
            }
        }

        int ans = 0;
        for (int i = 1; i <= n; i++) {
            if (count[i] == 0) ans++;
        }
        System.out.println(ans);
    }
}


Measured memory_bytes: 46248
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
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; }
#define all(x) (x).begin(),(x).end()
#define pll pair<ll,ll>
#define pii pair<int,int>
#define rep(i,n) for(int i=0;i<n;i++)
#define sz(x) ((ll)(x).size())
#define pb push_back
#define mp make_pair
#define bit(n) (1LL<<(n))
#define F first
#define S second
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
const ll INF = 1LL<<60;
const ll mod = (int)1e9 + 7;

int main() {
    ll n;
    cin >> n;
    ll a[n];
    ll b[n];
    rep(i,n){
        cin >> a[i];
        if(i==0)b[0]=a[0];
        else b[i]=b[i-1]+a[i];
    }
    ll ln=b[n-1];
    ll hf;
    rep(i,n){
        if(b[i]>ln/2){
            hf=i;
            break;
        }
    }
    if(hf==0)hf++;
    cout << min(abs(2*b[hf-1]-ln),abs(2*b[hf]-ln));
}

/*



 */


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

int main()
{
    int n,i,j;
    cin >> n;
    vector<pair<int,int>> red(n);
    vector<pair<int,int>> blue(n);
    for(i = 0;i < n;++i){
        cin >> red.at(i).second >> red.at(i).first;
    }
    for(i = 0;i < n;++i){
        cin >> blue.at(i).first >> blue.at(i).second;
    }
    sort(red.begin(),red.end(),greater<pair<int,int>>());
    sort(blue.begin(),blue.end());
    int ans = 0;
    for(i = 0;i < n;++i){
        for(j = 0;j < red.size();++j){
            if(red.at(j).first < blue.at(i).second && red.at(j).second < blue.at(i).first){
                ++ans;
                red.erase(red.begin()+j);
                break;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

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

int x, y, z;
int ta = 0;

int main() {
	cin >> x >> y >> z;
	for (int i = 1;; i++) {
		if (i*y + (i + 1)*z > x) {
			break;
		}
		else {
			ta = i;
		}
	}
	cout << ta << endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int main(void){
    
    char ch;
    int i ;
    int cou[26];
    
    for(i=0;i<26;i++) cou[i]=0;
    
    while(scanf("%c", &ch)!=EOF){
        if(ch==EOF) break;
            if('A' <= ch && ch<= 'Z')
                cou[ch-'A']++;
            if('a' <= ch && ch <= 'z')
                cou[ch-'a']++;

    }

    for(i=0;i<26;i++)
        printf("%c : %d\n", 'a'+i, cou[i]);
    
    return 0;
}

Measured memory_bytes: 540
import numpy as np
H,W = map(int,input().split())
S = np.array([list(input()) for _ in range(H)])
S = np.where(S=='.',1,0)


L = np.zeros((H,W),dtype=np.int)
R = np.zeros((H,W),dtype=np.int)
U = np.zeros((H,W),dtype=np.int)
D = np.zeros((H,W),dtype=np.int)

for i in range(W):
    L[:,i] = (L[:,i-1]+1)*S[:,i]
    R[:,-i-1] = (R[:,-i]+1)*S[:,-i-1]
for j in range(H):
    U[j,:] = (U[j-1,:]+1)*S[j,:]
    D[-j-1,:] = (D[-j,:]+1)*S[-j-1,:]

print(np.max(L+R+U+D)-3)


Measured memory_bytes: 250916
use std::io::*;
use std::str::FromStr;

pub fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let a: usize = read();
    let b: usize = read();

    if (a * 10 + b * 10) / 2 % 10 >= 5 {
        println!("{}", (a + b) / 2 + 1);
    } else {
        println!("{}", (a + b) / 2);
    }
}


Measured memory_bytes: 4352
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
 


public class Main {
	private static Scanner sc = new Scanner(System.in);
	//result = Math.pow(num1, num3)
	//StringBuffer str = new StringBuffer(hoge1);
	//String hoge2 = str.reverse().toString();
	//map.containsKey(A)

	//Map<String, Integer> map = new HashMap<String, Integer>(n);
	/*for ( キーのデータ型 key : マップの名前.keySet() ) {
		データのデータ型 data = マップの名前.get( key );
		
		// keyやdataを使った処理;
	}*/
	//int i = Integer.parseInt(s);
	//Queue<String> qq=new ArrayDeque<>(); //add,poll,peek
	//Deque<String> qq=new ArrayDeque<>();//push,pop,peek
	//ArrayList<String> cc = new ArrayList<>(n);
	//Collections.sort(list);
	//Array.sort(list);   cc.contains(tmp)
	//Arrays.asList(c).contains("a")
	//list.set(1,"walk");//1 1 2 3 5
	static long mod =1000000007;
	//static 	ArrayList<Integer> cc = new ArrayList<>(100);
	
	
	
	public static void main(String[] args) {
		//int N=sc.nextInt();for(int i=0;i<N;i++) {}
		
		int N=sc.nextInt();
	
		int v[]=new int[N];
		
		
		
		for(int i=0;i<N;i++) {
			v[i]=sc.nextInt()-1;
		}
		long ans=0;
		for(int i=0;i<N;i++) {
		
			if(v[i]==i) {
				ans++;
				if(i+1!=N&&v[i+1]==i+1) {
					v[i]=i+1;
					v[i+1]=i;
				}else if(i==0) {
					v[i]=v[i+1];
					v[i+1]=i;
				}else {
					v[i]=v[i-1];
					v[i-1]=i;
				}
				
				
			}
			
		}
		
		p(ans);
		

		
	
		
		
	}



	
	
	
	

	


	
	static void p(String ans) {System.out.println(ans);};
	static void p(int ans) {System.out.println(ans);};
	static void p() {System.out.println();};
	static void p(long ans) {System.out.println(ans);};
	static void p(double ans) {System.out.println(ans);};
	static String nextPermutation(String s) {
		ArrayList<Character> list=new ArrayList<>();
		for(int i=0;i<s.length();i++) {
			list.add(s.charAt(i));
		}
		int pivotPos=-1;
		char pivot=0;
		for(int i=list.size()-2;i>=0;i--) {
			if(list.get(i)<list.get(i+1)) {
				pivotPos=i;
				pivot=list.get(i);
				break;
			}
		}
		if(pivotPos==-1&&pivot==0) {
			return "Final";
		}
		int L=pivotPos+1,R=list.size()-1;
		
		
		
		int minPos=-1;
		char min =Character.MAX_VALUE;
		
		for(int i=R;i>=L;i--) {
			if(pivot<list.get(i)) {
				if(list.get(i)<min) {
					min=list.get(i);
					minPos=i;
				}
			}
		}
		
		Collections.swap(list, pivotPos, minPos);
		Collections.sort(list.subList(L, R+1));
		
		
		StringBuilder sb=new StringBuilder();
		for(int i=0;i<list.size();i++) {
			sb.append(list.get(i));
		}
		return sb.toString();
	}
}
	


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

ll n,m,on[12],ans=0,p[12];
vector<int>s[12];

void cal(){
	for(int i=0;i<m;i++){
		int cnt =0;
		for(int j=0;j<s[i].size();j++){
			if(on[s[i][j]]){
				cnt++;
			}
		}
		if(cnt%2!=p[i]){
			return;
		}
	}
	ans++;
}

void dep(int k){
	if(k==n){
		cal();
		return;
	}
	on[k]=0;dep(k+1);
	on[k]=1;dep(k+1);
}

int main() {
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int z;
		cin>>z;
		for(int j=0;j<z;j++){
			int x;
			cin>>x;
			x--;
			s[i].push_back(x);
		}
	}
	for(int i=0;i<m;i++){
		cin>>p[i];
	}
	dep(0);
	cout <<ans;
	return 0;
}

Measured memory_bytes: 256
import sys
import  math
import fractions
from collections import defaultdict
import bisect
stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

N,M=nm()
A=nl()
A.sort()
S=[0]
S[0]=A[0]

for i in range(1,N):
    S.append(S[i-1]+A[i])

def clc_shake(x):#x以上の和
    tot=0
    for i in range(N):
        th=x-A[i]
        inds=bisect.bisect_left(A,th)
        tot+=(N-inds)
    return tot

l=0
r=2*(10**6)
c=0

while (l+1<r):
    c=(l+r)//2
    if(clc_shake(c)<M):
        r=c
    else:
        l=c


ans=0
for i in range(N):
        th=r-A[i]
        inds=bisect.bisect_left(A,th)
        if(inds!=0):
            ans+=((N-inds)*A[i]+(S[N-1]-S[inds-1]))
        else:
            ans+=((N-inds)*A[i]+(S[N-1]))


M2=M-clc_shake(r)
ans+=M2*(l)
print(ans)





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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N;
map<ll,int> M[2];
ll A[3][101010];
vector<ll> V[2];
int RP[2];

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V operator()(int e) {V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	V add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
};

ll array_inv(vector<ll> V) {
	static BIT<int,18> bt;
	ZERO(bt.bit);
	int x=0,i;
	map<ll,int> M;
	vector<int> V2;
	
	M[-1LL<<60]=0;
	FORR(r,V) M[r]=0;
	FORR(r,M) r.second=x++;
	ll ret=0;
	for(i=V.size()-1;i>=0;i--) {
		ret += bt(M[V[i]]);
		bt.add(M[V[i]],1);
	}
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[0][i];
	FOR(i,N) cin>>A[1][i];
	FOR(i,N) cin>>A[2][i];
	
	FOR(i,N) {
		ll P=1+i*3, Q=P+1, R=Q+1;
		if(i%4>=2) swap(P,R);
		M[i%2][(P<<40)+(Q<<20)+R]=i/2;
	}
	FOR(i,N) {
		if(i%4>=2) swap(A[0][i],A[2][i]);
		ll k1=(A[0][i]<<40)+(A[1][i]<<20)+A[2][i];
		ll k2=(A[2][i]<<40)+(A[1][i]<<20)+A[0][i];
		if(M[i%2].count(k1)) V[i%2].push_back(M[i%2][k1]);
		else if(M[i%2].count(k2)) V[i%2].push_back(M[i%2][k2]), RP[i%2]^=1;
		else return _P("No\n");
	}
	
	if(array_inv(V[0])%2!=RP[1] || array_inv(V[1])%2!=RP[0]) return _P("No\n");
	_P("Yes\n");
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n';
	FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	solve(); return 0;
}


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

int main(){
  int n;
  string input;
  vector<int> result;

  cin>>n;

  for(int i=0;i<n;++i){
    int a,b;
    int s;
    
    cin>>input;

    sort(input.begin(),input.end(),greater<int>());
    a=stoi(input);

    sort(input.begin(),input.end());
    b=stoi(input);

    s=a-b;
    
    result.push_back(s);
  }

  for(auto i:result)
    cout<<i<<endl;

}

Measured memory_bytes: 3168
import java.io.FileNotFoundException;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Scanner;

class Main {

	class BIT {
		int n;
		long[] v;

		public BIT(int n_) {
			n = n_;
			v = new long[n + 1];
		}

		void add(int k, int val) {
			while (k <= n) {
				v[k] += val;
				k += k & -k;
			}
		}

		long sum(int k) {
			long ret = 0;
			while (k >= 1) {
				ret += v[k];
				k -= k & -k;
			}
			return ret;
		}

		long sum(int l, int r) {
			return sum(r - 1) - sum(l - 1);
		}
	}

	void run() {
		Scanner sc = new Scanner(System.in);
		String S = sc.next();
		int[] cnt = new int[26];
		int[] cnt2 = new int[S.length()];
		for (int i = 0; i < S.length(); ++i) {
			++cnt[S.charAt(i) - 'a'];
			cnt2[i] = cnt[S.charAt(i) - 'a'];
		}
		boolean f = true;
		for (int i = 0; i < cnt.length; ++i) {
			if (cnt[i] % 2 != 0) {
				if (!f) {
					System.out.println(-1);
					return;
				} else {
					f = false;
				}
			}
		}
		for (int i = 0; i < S.length(); ++i) {
			if (cnt[S.charAt(i) - 'a'] % 2 == 1) {
				if (cnt2[i] <= (cnt[S.charAt(i) - 'a'] - 1) / 2)
					cnt2[i] = 1;
				else if (cnt2[i] == (cnt[S.charAt(i) - 'a'] + 1) / 2)
					cnt2[i] = 2;
				else
					cnt2[i] = 3;
			} else {
				if (cnt2[i] <= cnt[S.charAt(i) - 'a'] / 2) {
					cnt2[i] = 1;
				} else {
					cnt2[i] = 3;
				}
			}
		}

		BIT bit = new BIT(3);
		long ans = 0;

		for (int i = 0; i < S.length(); ++i) {
			ans += bit.sum(cnt2[i] + 1, 4);
			bit.add(cnt2[i], 1);
		}

		ArrayDeque<Integer>[] dq = new ArrayDeque[26];
		for (int i = 0; i < dq.length; ++i)
			dq[i] = new ArrayDeque();

		int p = 1;
		for (int i = S.length() - 1; i >= 0; --i) {
			if (cnt2[i] == 3) {
				dq[S.charAt(i) - 'a'].addLast(p++);
			}
		}
		BIT bit2 = new BIT(S.length());
		for (int i = 0; i < S.length(); ++i) {
			if (cnt2[i] == 1) {
				int j = dq[S.charAt(i) - 'a'].pollFirst();
				ans += bit2.sum(j + 1, S.length() + 1);
				bit2.add(j, 1);
			}
		}
		System.out.println(ans);
	}

	void tr(Object... objects) {
		System.out.println(Arrays.deepToString(objects));
	}

	public static void main(String[] args) throws FileNotFoundException {
		new Main().run();
	}
}


Measured memory_bytes: 32608
#include<bits/stdc++.h>
using namespace std;
string c;
int main(){
	cin>>c;
	if(c[0]=='7'){cout<<"Yes";return 0;}
	if(c[1]=='7'){cout<<"Yes";return 0;}
	if(c[2]=='7'){cout<<"Yes";return 0;}
	cout<<"No";
	return 0;
}

Measured memory_bytes: 3592
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define rep1(i,n) for(int i=1;i<=(int)n;i++)
#define rep2(i,j,n) for(int j=i;j<n;j++)
#define rep3(i,j,n) for(int j=i;j<=n;j++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define sp(n) cout << fixed << setprecision(n)
typedef long long ll;
using namespace std;
int main(void){
    int n;cin>>n;
    string s;cin>>s;
    vector<int> r,g,b;
    rep(i,n){
        char x=s[i];
        if(x=='R')r.push_back(i);
        else if(x=='B')b.push_back(i);
        else g.push_back(i);
    }
    int rs=r.size(),bs=b.size(),gs=g.size();
    //b.push_back(-1);
    //b.push_back(-1);
    ll res=0;
    
    rep(i,rs){
        rep(j,gs){
            int R=r[i],G=g[j];
            if((R+G)%2==0){
                int mid=(R+G)/2;
                auto itr=lower_bound(b.begin(),b.end(),mid),itr2=upper_bound(b.begin(),b.end(),mid);
                int k=itr-b.begin(),k2=itr2-b.begin();
                if(k2-k)res--;
            }
            if(R<G){    
                int buf=G-R;
                auto itr=lower_bound(b.begin(),b.end(),R-buf),itr2=upper_bound(b.begin(),b.end(),R-buf);
                int k=itr-b.begin(),k2=itr2-b.begin();
                if(k2-k)res--;
                itr=lower_bound(b.begin(),b.end(),G+buf),itr2=upper_bound(b.begin(),b.end(),G+buf);
                k=itr-b.begin(),k2=itr2-b.begin();
                if(k2-k)res--;
            }
            else{
                int buf=R-G;
                auto itr=lower_bound(b.begin(),b.end(),G-buf),itr2=upper_bound(b.begin(),b.end(),G-buf);
                int k=itr-b.begin(),k2=itr2-b.begin();
                if(k2-k)res--;
                itr=lower_bound(b.begin(),b.end(),R+buf),itr2=upper_bound(b.begin(),b.end(),R+buf);
                k=itr-b.begin(),k2=itr2-b.begin();
                if(k2-k)res--;
            }
            res+=bs;
        }
    }
    cout<<res<<endl;
}

Measured memory_bytes: 3640
#include<stdio.h>
int main()
{
	int n, m , i=0, j=0, sum1=0, sum2=0, count=0;
  	scanf("%d%d", &n , &m);
  for(i=1; i<=n; i++)
  {
    sum1 = sum1+(n-i);
  }
    for(j=1; j<=m; j++)
    {
     sum2 = sum2+(m-j);
    }
  count= sum1+sum2;
  printf(" %d ",count);
  return 0;
}

Measured memory_bytes: 128
// AOJ 2610: Fast Division
// 2017.10.6 bal4u@uu

#include <stdio.h>

int ans[4] = { 1, 2, 1, 0 };
int main()
{
	int n;

	scanf("%d", &n);
	if (n > 2) n = 3;
	printf("%d\n", ans[n]);
	return 0;
}

Measured memory_bytes: 1820
#include<stdio.h>

int main() {
	int loop;
	int A[100000];
	int N, T;
	int min = 1000000001;
	int gain = 0;
	int ans;
	scanf("%d %d", &N, &T);
	for (loop = 0; loop < N; loop++)scanf("%d", &A[loop]);

	for (loop = 0; loop < N; loop++) {
		if (min > A[loop])min = A[loop];
		else if (min < A[loop]) {
			if (gain < A[loop] - min) {
				gain = A[loop] - min;
				ans = 1;
			}
			else if (gain == A[loop] - min)ans++;
		}
	}
	printf("%d\n", ans);
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back 
#define what_is(x) cerr<<#x<<" is "<<x<<endl;
#define print(v) for(auto i:v) cout<<i<<" ";cout<<endl;
#define time_kam_hai ios_base::sync_with_stdio(false);cin.tie(NULL);
#define fi first
#define se second
#define all(v) v.begin(),v.end()
#define ll long long 
#define endl "\n"
#define vi vector<int> ;
#define vii vector<pair<int,int>> 
#define vl vector<long long int>
#define vll vector<ll,ll> 
#define MOD 1000000007
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
typedef tree<int, null_type, less<int>, rb_tree_tag, 
             tree_order_statistics_node_update> 
    ordered_set; 
//find_by_order(x)
//order_of_key(x)  
void computeLPSArray(string pat, int M, int* lps); 


int power(int x,unsigned int y)
{
    int res=1;
    
    while(y>0)
    {
        // if y is odd multiply with result
        if(y&1)
        res=res*x;
        
        y=y>>1; // y=y/2;
        x=x*x;
        
    }
    return res;
}

int  main(){
	time_kam_hai;
	int t;
	t=1;
	//cin >> t;
	while(t--){
	    
	    string str;
	    cin>>str;
	    
	    cout<<str.substr(0,3)<<endl;
	    
	}
	return 0;
}






Measured memory_bytes: 3644
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;
 
int main() {
    ll n, m;
    cin >> n >> m;

    vl s(n);
    rep(i, n) {
        cin >> s[i];
    }

    vl t(m);
    rep(i, m) {
        cin >> t[i];
    }

    vvl dp(n, vl(m));  // s[i]までとt[j]までで、s[i]とt[j]を使用するときの整数列として等しい部分列の個数
    vvl rui(n+1, vl(m+1));  // Σ dp[x][y] (0 <= x < i, 0 <= y < j)
    rep(i, n) {
        rep(j, m) {
            if(s[i] == t[j]) {
                dp[i][j] = (rui[i][j] + 1)%mod;
            }
            rui[i+1][j+1] = (rui[i+1][j] + rui[i][j+1] + mod - rui[i][j] + dp[i][j])%mod;
        }
    }
    
    out((rui[n][m] + 1)%mod);
    re0;
}

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

const int N = 200010;

char s[N];
int n, k;
std::deque <int> dq;

int main(){
	scanf("%d%d%s", &n, &k, s);
	for (int i = 0; i < n; ++ i){
		dq.push_back(s[i] - 'A');
	}
	if (k > n << 1){
		k = (n << 1) + (k & 1);
	}
	int flag = 0;
	for (int i = 0; i < k; ++ i){
		int x = dq.front();
		if (x == flag){
			dq.pop_front();
			dq.push_front(flag ^ 1);
		}
		else{
			dq.pop_front();
			flag ^= 1;
			dq.push_back(flag);
		}
	}
	while (!dq.empty()){
		int x = dq.front();
		putchar((x ^ flag) + 'A');
		dq.pop_front();
	}
	return printf("\n"), 0;
}

Measured memory_bytes: 1536
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(x) x.begin(),x.end()

int const N = 200001;

int main(){
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    if(min({a, b, c}) == max({a, b,c}))puts("No");
    else {
        if(a == b || a == c || b == c)puts("Yes");
        else puts("No");
    }  
} 

Measured memory_bytes: 256
#include <stdio.h>          // printf(), scanf(), getchar()
#include <stdbool.h>

int
main(int argc, char** argv)
{
	int dx[7][4] = {{0, 1, 0, 1}, {0, 0, 0, 0}, {0, 1, 2, 3}, {1, 0, 1, 0}, {0, 1, 1, 2}, {0, 0, 1, 1}, {1, 2, 0, 1}};
	int dy[7][4] = {{0, 0, 1, 1}, {0, 1, 2, 3}, {0, 0, 0, 0}, {0, 1, 1, 2}, {0, 0, 1, 1}, {0, 1, 1, 2}, {0, 0, 1, 1}};
	int x, y;
	int nx, ny;
	int i, j;
	int c;

	while (true)
	{
		char mat[8][9];
		for (i = 0; i < 8; ++i)
			scanf("%s", &mat[i][0]);

		for (y = 0; y < 8; ++y)
		{
			for (x = 0; x < 8; ++x)
			{
				for (i = 0; i < 7; ++i)
				{
					for (j = 0; j < 4; ++j)
					{
						nx = x + dx[i][j], ny = y + dy[i][j];
						if (nx >= 8 || ny >= 8 || mat[ny][nx] == '0')
							break;
					}

					if (j >= 4)
					{
						printf("%c\n", 'A' + i);
						goto l_done;
					}
				}
			}
		}

l_done:
		c = getchar();
		if (c != '\n')
			break;

		c = getchar();
		if (c == EOF)
			break;
	}

	return 0;
}

Measured memory_bytes: 540
#include <iostream>
#include <vector>

using namespace std;

#define f(i, n) for(int i = 1; i <= n; i++)

const int N = 1005;
const int M = 100005;
const long long inf = 1e18;

// long long dp[N][M];

int main (){

  int n, g, *v, *w, maxi = 0;
  long long sm = 0, x = 0;

  cin >> n >> g;

  v = new int[n + 1];
  w = new int[n + 1];
  f(i, n){
    cin >> w[i] >> v[i];
    //maxi = (v[i] < maxi ? maxi : v[i]);
    sm += v[i];
  }

  vector<vector<long long>> dp( N, vector<long long>( M, inf ));

  dp[0][0] = 0;

  for (int i = 1; i <= n; i++ )
    for ( int j = 0; j <= sm; j++ ){
      if (j >= v[i] && dp[i - 1][j - v[i]] !=  inf )
        dp[i][j] = min( dp[i - 1][j], (long long) w[i] + dp [i - 1][j - v[i]]);
      else dp[i][j] = dp[i - 1][j];
      if( dp[n][j] <= g )
        x = max ( x, (long long)j );
  }

  cout << x ;

  delete( v );
  delete( w );

  return 0;
}


Measured memory_bytes: 788992
#include<stdio.h>
main(){
  int n,a,b,c,i,j;
  while(scanf("%d %d",&a,&b) != EOF){
    n = 0;
    c = a+b;
    while(1){
      if(c < 1)break;
      c = c/10;
      n++;
    }
    printf("%d\n",n);
  }
  return 0;
}

Measured memory_bytes: 600
#include <iostream>
#include <cstring>

using namespace std;

const int N = 8e5;
int n, t, pre[N], last[N], tar[N], q[N], l, r, h[N];
void add(int x, int y)
{
    t++;
    pre[t] = last[x];
    tar[t] = y;
    last[x] = t;
}

void bfs(int st)
{
    l = 1, r = 1;
    q[1] = st;
    memset(h, 0, sizeof(h));
    h[st] = 1;
    while (l <= r)
    {
        int x = q[l++];
        for (int ptr = last[x]; ptr; ptr = pre[ptr])
        {
            int xx = tar[ptr];
            if (!h[xx])
            {
                q[++r] = xx;
                h[xx] = h[x] + 1;
            }
        }
    }
}

int main()
{
    cin >> n;
    for (int i = 1; i < n; i++)
    {
        int x, y;
        cin >> x >> y;
        add(x, y);
        add(y, x);
    }
    bfs(1);
    bfs(q[r]);
    if (h[q[r]] % 3 != 2) cout << "First";
    else cout << "Second"  << endl;
    return 0;
}

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

#define each(i, c) for (auto& i : c)
#define mkp(a, b) make_pair(a, b)

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> Pll;
const ll MOD = 1e9+7;

template<typename P, typename Q> ostream& operator << (ostream& os, pair<P, Q> p) { os << "(" << p.first << ": " << p.second << ")"; return os; }
template<typename T> ostream& operator << (ostream& os, vector<T> v) { os << "("; each (i, v) os << i << ", "; os << ")"; return os; }
template<typename K, typename V> ostream& operator << (ostream& os, map<K, V> m) { os << "{"; each (i, m) os << i << ", "; os << "}"; return os; }

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

  vector<ll> a(n);
  for (ll i = 0; i < n; ++i) {
    cin >> a[i];
  }
  sort(a.begin(), a.end(), greater<ll>());

  Pll ans = mkp(a[0], a[1]);
  ll mid = a[0] / 2;
  ll diff = abs(mid - a[1]);
  for (ll i = 2; i < n; ++i) {
    ll d = abs(mid - a[i]);
    if (d < diff) {
      ans = mkp(a[0], a[i]);
      diff = d;
    }
  }

  cout << ans.first << " " << ans.second << endl;

  return 0;
}

Measured memory_bytes: 1024
n, m = map(int, input().split())
k = []
s = []
for _ in range(m):
    l = list(map(int, input().split()))
    k.append(l[0])
    s.append(l[1:])
p = list(map(int, input().split()))

b = []
for i in range(2 ** n):
    tmp = [0] * (n)
    for j in range(n):
        if i >> j & 1:
            tmp[j] = 1
    b.append(tmp)
    
ans = 0
for i in range(2 ** n):
    bc = b[i]
    flag = True
    for j in range(m):
        t = 0
        for onsw in s[j]:
            t += bc[onsw - 1]
        if t%2 != p[j]:
            flag = False
    if flag:
        ans += 1
    
print(ans)

Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
const int N=200000+10;
const int INF=10000000;
int p1[N],p2[N];
map<pair<int,int>,int>m;
int find(int x,int *p)
{
    return p[x]==x?p[x]:p[x]=find(p[x],p);
}
void cha(int x,int y,int *p)
{
    int px=find(x,p);
    int py=find(y,p);
    if(px!=py)
    {
        p[px]=py;
    }
}
int main()
{
    int n,k,l;
    cin>>n>>k>>l;
    for(int i=1;i<=n;i++)
        p1[i]=i,p2[i]=i;
    for(int i=1;i<=k;i++)
    {
        int x,y;
        scanf("%d%d,",&x,&y);
        cha(x,y,p1);
    }
    for(int i=1;i<=l;i++)
    {
        int x,y;
        scanf("%d%d,",&x,&y);
        cha(x,y,p2);
    }
    for(int i=1;i<=n;i++)
    {
        find(i,p1);
        find(i,p2);
    }
    for(int i=1;i<=n;i++)
        m[make_pair(p1[i],p2[i])]++;
    for(int i=1;i<=n;i++)
        printf("%d ",m[make_pair(p1[i],p2[i])]);
    return 0;
}


Measured memory_bytes: 13568
#include <cstdio>
#include <algorithm>  
#include <bitset>
#include <cassert>
#include <ctime>  
#include <cmath>  
#include <cstdlib>  
#include <cstring>  
#include <functional>  
#include <iostream>  
#include <deque>  
#include <stack>
#include <queue>  
#include <vector>  
#include <map>  
#include <set>  
#include <string>  
#include <unordered_map>  
#include <unordered_set>  
#pragma warning(disable:4996)

using namespace std;

#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define endl '\n'

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, int> pdi;

const int INF = 1e9;
const int MAXN = 1e5 + 5;

int N, M, dp[105][105];
char A[105][105];

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> N >> M;
	for(int i=1; i<=N; i++) cin >> A[i]+1;

	dp[1][1] = A[1][1] == '#';

	for(int i=1; i<=M; i++) dp[0][i] = INF;
	for(int i=1; i<=N; i++) dp[i][0] = INF;

	for(int i=1; i<=N; i++) {
		for(int j=1; j<=M; j++) {
			if(i == 1 && j == 1) continue;
			int a = dp[i][j-1] + (A[i][j] == '#' && A[i][j] != A[i][j-1]);
			int b = dp[i-1][j] + (A[i][j] == '#' && A[i][j] != A[i-1][j]);
			dp[i][j] = min(a, b);
		}
	}
	cout << dp[N][M];
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
#define mrep(i,j,n) for(int i = j; i < n; i++)
#define reps(i,n) for(int i = 1; i <= n; i++)
#define rrep(i,n) for(int i = n-1; i >= 0; i--)
#define rreps(i,n) for(int i = n; i >= 1; i--)
#define co(x) cout << x <<endl
#define cs(x) cout << x <<" "
#define cer(x) cerr << x <<endl
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define ERASE(x,val) x.erase(remove(ALL(x), val), x.end())

typedef long long ll;
typedef unsigned long long ull;
using namespace std;
ll mod = 1e9 + 7;
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; }

int main()
{
	string s; cin >> s;
	int k = sz(s);
	int win = 0;
	rep(i, k)if (s[i] == 'o')++win;
	if (win + 15 - k >= 8)co("YES");
	else co("NO");
	return 0;
}


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

int main(){
    int S;
    cin >> S;
    int h, min, sec;
    h = S/3600;
    min = (S % 3600) / 60;
    sec = S - 3600*h - min * 60;
    cout << h << ':'<< min << ':' << sec << endl;
    return 0;
}


Measured memory_bytes: 3092
from collections import defaultdict
n, a, d = map(int, input().split())
if d == 0:
    print(1 if a == 0 else n + 1)
    exit()
if d < 0:
    a, d = -a, -d
dic = defaultdict(list)
for i in range(n + 1):
    l = a * i + (i - 1) * i // 2 * d
    r = a * i + (n - i + n - 1) * i // 2 * d
    dic[l % d].append((l, r))
res = 0
for p in dic.values():
    p.sort()
    r = -1000000000000000000
    for t in p:
        s, e = t
        if r < s:
            res += (e - s) // d + 1
            r = e
        if r < e:
            res += (e - r) // d
            r = e
print(res)

Measured memory_bytes: 72552