akhauriyash/Code-Regression huggingface dataset:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<stack>
#include<queue>
using namespace std;
typedef long long ll;

//const int maxn
int n,m,k,cnt,ans,co;
int a[10];
int row[10],col[10];
char mp[10][10];

ll read(){ ll s=0,f=1; char ch=getchar(); while(ch<'0' || ch>'9'){ if(ch=='-') f=-1; ch=getchar(); } while(ch>='0' && ch<='9'){ s=s*10+ch-'0'; ch=getchar(); } return s*f; }

void dfs2(int c){
	if(c==(m+1)){
//		++co;
//		printf("%d:\n",co);
//		for(int i=1;i<=n;i++){
//			printf("%d ",row[i]);
//		} printf("\n");
//		for(int i=1;i<=m;i++){
//			printf("%d ",col[i]);
//		} printf("\n");
		for(int i=1;i<=n;i++)
		{	
			for(int j=1;j<=m;j++){
				if((mp[i][j]=='#')&&(!row[i])&&(!col[j])) ++cnt;
			}
		}
		if(cnt==k){
			++ans;
		}
		cnt=0;
		return;
	}
	col[c]=1;
	dfs2(c+1);
	col[c]=0;
	dfs2(c+1);
}

void dfs1(int r){
	if(r==(n+1)){
		dfs2(1);
		for(int i=1;i<=m;i++) col[i]=0;
		return;
	}
	row[r]=1;
	dfs1(r+1);
	row[r]=0;
	dfs1(r+1);
}

int main(){
	cnt=0,ans=0;
	n=read(),m=read(),k=read();
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>mp[i][j];
		}
	}

	dfs1(1);
	
	printf("%d\n",ans);
//	printf("%d\n",cnt);
//	for(int i=1;i<=n;i++){
//		for(int j=1;j<=m;j++){
//			printf("%c",mp[i][j]);
//		}
//		printf("\n");
//	}
	return 0;
}


Measured memory_bytes: 3704
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n;
  int cnt, temp;
  
  cin >> n;
  
  if(n >= 105){
    cnt = 1;
    for(int i = 107;i <= n;i += 2){
      temp = 0;
      for(int j = 1;j <= i;j++){
	if(i % j == 0) temp++;
      }
      if(temp == 8) cnt++;
    }
    cout << cnt << endl;
  }else{
    cout << 0 << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define finish(x) return cout << x << endl, 0
#define ll long long

const int N = 101;

int n, m, dp[N][N];
vector <string> a;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    a.resize(n);
    for(auto &i : a) cin >> i;
    dp[0][0] = a[0][0] == '#';
    for(int i = 0 ; i < n ; i++){
        for(int j = 0 ; j < m ; j++){
            if(i == 0 && j == 0) continue;
            dp[i][j] = 1e9;
            if(i > 0) dp[i][j] = min(dp[i][j], dp[i - 1][j] + (a[i - 1][j] == '.' && a[i][j] == '#'));
            if(j > 0) dp[i][j] = min(dp[i][j], dp[i][j - 1] + (a[i][j - 1] == '.' && a[i][j] == '#'));
        }
    }
    cout << dp[n - 1][m - 1] << endl;
}


Measured memory_bytes: 384
from sys import stdin
n = int(stdin.readline().rstrip())
s = list(stdin.readline().rstrip())
wl = [0]
el = [0]
ans=[]
for i in range(n):
    wl.append(wl[i]+1 if s[i] == 'W' else wl[i])
for i in range(n):
    el.append(el[i]+1 if s[i] == 'E' else el[i])
for i in range(n+1):
    ans.append(wl[i]+el[-1]-el[i])
print(min(ans))

Measured memory_bytes: 31736
//b.c B-Ruined Square
#include<stdio.h>
int iabs(int x){
    if(x<0){
        return -x;
    }
    return x;
}

int main(void){
    int x1,x2,x3,x4,y1,y2,y3,y4;
    scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
    int x = x2-x1,y = y2-y1;
    printf("%d %d %d %d\n",x2-y,y2+x,x1-y,y1+x);
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vs = vector<string>;
using pll = pair<ll, ll>;
using vp = vector<pll>;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repb(i, n) for (int i = (n-1); i >= 0; i--)
#define rea(i, a, b) for (int i = (a); i < (b); i++)
#define reab(i, a, b) for (int i = (a)-1; i >= (b); i--)
#define ALL(a) (a).begin(),(a).end()
#define SZ(x) ((int)(x).size())
#define PRINT(V) for (auto v:(V)) {cerr << v << " ";} cerr << endl
#define dump(x) cerr << #x << " : " << (x) << endl
#define dump2(x, y) cerr << "(" << #x << ", " << #y << ") = (" << x << ", " << y << ")" << endl
inline ll GCD(ll a, ll b){return b ? GCD(b, a % b) : a;}
const int MOD = 1000000007;
/* END OF TEMPLATE */

int main(){
    ll N, M;
    cin >> N >> M;
    vll P(M), Y(M), x(M);
    vll yd[100001];
    rep(i, M){
        cin >> P[i] >> Y[i];
        yd[P[i]].push_back(Y[i]);
    }
    rep(i, N){
        sort(ALL(yd[i+1]));
    }
    rep(i, M){
        x[i] = 1 + distance(yd[P[i]].begin(), lower_bound(ALL(yd[P[i]]), Y[i]));
        cout << setfill('0') << setw(6) << right << P[i];
        cout << setfill('0') << setw(6) << right << x[i] << endl;
    }
}

Measured memory_bytes: 9344
#include <algorithm>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <iomanip>
#include <iterator>
#include <map>
#include <numeric>
#include <queue>
#include <regex>
#include <set>
#include <string>
#include <vector>
using namespace std;
 
#define rep(i,x) for(int i=0;i<(int)(x);++i)
#define reps(i,x) for(int i=1;i<=(int)(x);++i)
#define rrep(i,x) for(int i=((int)(x)-1);i>=0;i--)
 
long long int s, t;

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

    t = s;
    long long int sum = 0;
    while (1) {
        sum += s%10;
        s /= 10;
        if (s == 0) {
            break;
        }
    }

    if (t%sum == 0) {
        cout << "Yes" << '\n';
    } else {
        cout << "No" << '\n';
    }

    return 0;
}

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

int main()
{
  int n;
  cin>>n;
  
  int arr[n+1];
  for(int i=1;i<=n;i++)
    cin>>arr[i];
  
  int ans=0;
  
  for(int i=1;i<=n;i+=2)
    if(arr[i]%2 != 0)
      ans++;
  
  cout<<ans;
}


Measured memory_bytes: 3604
#include <iostream>
#include <deque>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <string.h>
#include <cmath>

using namespace std;
typedef long long i64;
typedef long double ld;
typedef pair<i64,i64> P;
#define rep(i,s,e) for(int (i) = (s);(i) <= (e);++(i))

struct edge
{
	int to;
	int cost;
};

const int MAX = 202020;

vector<edge> edges[3 * MAX];

map<P,int> seed;

int n;
int m;

int getID(int i,int c)
{
	if(seed.count({i,c})) return seed[P(i,c)];
	return seed[P(i,c)] = seed.size();
}

int p[MAX];
int q[MAX];
int c[MAX];


int main()
{
	cin >> n >> m;
	for(int i = 0;i < m;i++)
	{
		cin >> p[i] >> q[i] >> c[i];
		int s = getID(p[i] , c[i]);
		int t = getID(q[i] , c[i]);
		edges[s].push_back({t,0});
		edges[t].push_back({s,0});
	}
	int last = seed.size();
	for(int i = 0;i < m;i++)
	{
		// p side
		{
			int kai = last + p[i];
			edges[getID(p[i],c[i])].push_back({last + p[i] , 0});
			edges[last + p[i]].push_back({getID(p[i],c[i]),1});
		}
		// q side
		{
			int kai = last + q[i];
			edges[getID(q[i],c[i])].push_back({last + q[i] , 0});
			edges[last + q[i]].push_back({getID(q[i],c[i]),1});
		}
	}

	vector<int> dist(n + last + 5,1e9);

	{
		deque<P> que;
		que.push_front({0,1 + last});
		dist[1 + last] = 0;

		while(!que.empty())
		{
			int v = que.front().second;
			int d = que.front().first;
			que.pop_front();

			if(dist[v] < d) continue;

			for(auto& e : edges[v])
			{
				if(dist[e.to] > d + e.cost)
				{
					dist[e.to] = d + e.cost;
					if(e.cost)
						que.push_back({dist[e.to] , e.to});
					else
						que.push_front({dist[e.to],e.to});
				}
			}
		}
	}

	if(dist[n + last] == 1e9)
		dist[n + last] = -1;
	cout << dist[n + last] << endl;

}

			


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

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

  string S; cin >> S;
  int K; cin >> K;

  int len = S.size();
  int K_MAX = 4;
  vector<vector<ll>> eq(len, vector<ll>(K_MAX + 1, 0));
  vector<vector<ll>> lt(len, vector<ll>(K_MAX + 1, 0));

  eq[0][1] = 1;
  lt[0][1] = S[0] - '1';
  lt[0][0] = 1;

  for (ll i = 1; i < len; i++) {
    int d = S[i] - '0';
    for (ll k = 0; k < K_MAX; k++) {
      if (d == 0) {
        eq[i][k] += eq[i - 1][k];
      } else {
        eq[i][k + 1] += eq[i - 1][k];
        lt[i][k + 1] += eq[i - 1][k] * (d - 1);
        lt[i][k] += eq[i - 1][k];
      }
      lt[i][k + 1] += lt[i - 1][k] * 9;
      lt[i][k] += lt[i - 1][k];
    }
  }

  cout << (eq[len - 1][K] + lt[len - 1][K]) << '\n';
  return 0;
}

Measured memory_bytes: 256
#include <iostream>

int main()
{
	long N, K;
	std::cin >> N >> K;

	long counter1 = 0, counter2 = 0;

	for ( long i = 1; i <= N; i++ )
	{
		if ( ( i % K ) == 0 )
		{
			++counter1;
		}
		else if ( ( ( K & 1 ) == 0 )
				  && ( ( i % K ) == ( K / 2 ) )
			)
		{
			++counter2;
		}
	}

	long result;
	result = counter1 * counter1 * counter1;
	result += counter2 * counter2 * counter2;

	std::cout << result << std::endl;

	return ( 0 );
}


Measured memory_bytes: 888
#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
#define FOR(i, m, n) for (int i = (m); i < (n); i++)
#define FORR(i, m, n) for (int i = (m); i >= (n); i--)
#define REP(i, n) FOR(i, 0, (n))
#define REPR(i, n) FORR(i, (n) - 1, 0)
#define REP1(i, n) FOR(i, 1, (n) + 1)
#define REPS(c, s) for (char c : s)
#define ALL(c) (c).begin(), (c).end()
#define SORT(c) sort(ALL(c))
#define REV(c) reverse(ALL(c))
#define sz(v) (int)v.size()
#define endl '\n'
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
template<class T> inline void printv(vector<T>& v) {int n = sz(v); REP(i, n) cout << v[i] << (i == n - 1 ? endl : ' ');}
template<class T> inline void printvv(vector<vector<T>>& v) {for (auto u : v) printv(u);}
template<class T> inline void printlnv(vector<T>& v) {int n = sz(v); REP(i, n) cout << v[i] << endl;}
const int MOD = 1000000007;
const int INF = 1000000001;
const ll LINF = 1000000001000000001LL;
 
void solve();
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(numeric_limits<double>::max_digits10);
    solve();
    return 0;
}

void solve() {
    int n;
    cin >> n;
    vl a(n);
    int m = 0;
    ll mn = INF;
    REP(i, n) {
        cin >> a[i];
        if (a[i] < 0) m++;
        a[i] = abs(a[i]);
        chmin(mn, a[i]);

    }
    ll ans = accumulate(ALL(a), 0LL);
    if (m % 2 == 1) ans -= mn * 2;
    cout << ans << endl;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int c1 = 0, c2 = 0;
    string s;
    getline(cin, s);
    for (int i = 0; i < s.length(); ++i)
    {
        if (s[i] == '1')
            ++c1;
        else
            ++c2;
    }
    if (c1 == 0)
        cout << 0 << endl;
    else if (c2 == 0)
        cout << 0 << endl;
    else
        cout << min(c1, c2) * 2 << endl;
    return 0;
}

Measured memory_bytes: 512
import java.util.Arrays;
import java.util.Scanner;

public class Main {

     static Scanner scanner;

     public static void main(String[] args) {
         scanner = new Scanner(System.in);

         int N=gi();
         int[] a=new int[N];
         for(int i=0; i<N;i++) {
        	 a[i]=gi();
         }
         Arrays.parallelSort(a);

         int n=a[N-1];
         int r=a[0];

         for (int i=0; i<N-1;i++) {
        	 int t=Math.min(a[i], n-a[i]);
        	 int rt=Math.min(r, n-r);
        	 if(t>rt) {
        		 r=a[i];
        	 }
         }

         System.out.println(n+" "+r);
         //System.out.println(ans);
     }

     // 文字列として入力を取得
     public static String gs() {
          return scanner.next();
     }

     // intとして入力を取得
     public static int gi() {
          return Integer.parseInt(scanner.next());
     }

     // longとして入力を取得
     public static long gl() {
          return Long.parseLong(scanner.next());
     }

     // doubleとして入力を取得
     public static double gd() {
          return Double.parseDouble(scanner.next());
     }
}

Measured memory_bytes: 61168
N, X = map(int, input().split())
L = list(map(int, input().split()))
D = []
D.append(0)
count = 0
for i in range(N):
    if(D[i]+L[i] > X):
        break
    else:
        D.append(D[i]+L[i])
        count += 1
print(count+1)

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

int main() {
  int N; cin >> N;
  if(N==0){
    cout << 0 << endl;
    return 0;
  }
  
  int digit[40]={};
  if(N>0){
    bitset<40> bit=bitset<40>(N);
    for(int i=0; i<40; i++){
      if(bit[i]==1){
        if(i%2==0){
          digit[39-i]++;
        }else{
          digit[39-i]++;
          digit[38-i]++;
        }
      }
    }
  }else{
    N=-N;
    bitset<40> bit=bitset<40>(N);
    for(int i=0; i<40; i++){
      if(bit[i]==1){
        if(i%2==0){
          digit[39-i]++;
          digit[38-i]++;
        }else{
          digit[39-i]++;
        }
      }
    }
  }
  for(int i=0; i<40; i++){
    if(digit[39-i]>1){
      int temp=digit[39-i]/2;
      digit[39-i]%=2;
      digit[38-i]+=temp;
      digit[37-i]+=temp;
    }
  }
  int k=0;
  while(digit[k]==0){
    k++;
  }
  for(int i=k; i<40; i++){
    cout << digit[i];
  }
  cout << endl;
}

Measured memory_bytes: 256
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
     
const int maxn(1e5 + 5);
     
int n, m, b[maxn], nxt[maxn], que[maxn], len, vis[maxn];
ll k, f[maxn], g[maxn];
     
int main() {
	int i, j;
	scanf("%d", &n);
	for (i = 1; i <= n; ++i) scanf("%lld", &f[i]), b[i] = i;
	for (i = n; i; --i) f[i] -= f[i - 1];
	scanf("%d%lld", &m, &k);
	for (i = 1; i <= m; ++i) scanf("%d", &j), swap(b[j], b[j + 1]);
	for (i = 1; i <= n; ++i)
		if (!vis[i]) {
			vis[i] = 1, j = b[i], que[len = 1] = i;
			while (!vis[j]) que[++len] = j, vis[j] = 1, j = b[j];
			for (j = 1; j <= len; ++j) nxt[que[j]] = que[(k + j - 1) % len + 1];
		}
	for (i = 1; i <= n; ++i) g[i] = f[nxt[i]];
	for (i = 1; i <= n; ++i) g[i] += g[i - 1], printf("%lld\n", g[i]);
	return 0;
}

Measured memory_bytes: 4352
import sys
x={}
for line in sys.stdin:
    for l in line:
        if l.isalpha():
            c=l.lower()
            x[c]=x.get(c,0)+1
for i in range(26):
    c=chr(ord("a")+i)
    print(f'{c} : {x.get(c,0)}')


Measured memory_bytes: 5580
#include <bits/stdc++.h>
using namespace std;
int main()
{
  int a;
  int x[2] = {0};

  //input
  for(int i=0;i<3;i++){
    cin>>a;
    if(a==5)
      x[0]+=1;
    if(a==7)
      x[1]+=1;
  }
  cout<<((x[0]==2 && x[1]==1)?"YES":"NO")<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <ios>
#include <iomanip>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <utility>
#include <typeinfo>
#include <tuple>
using namespace std;

#define MOD 1000000007
#define INF 1e9+7
#define INF_LONG 1e18
#define rep(i, n) for(int i=0; i<n; ++i)
#define rep1(i, n) for(int i=1; i<=n; ++i)
#define rrep(i, m, n) for(int i=m; i<n; ++i)
#define countof(array) (sizeof(array) / sizeof(array[0]))
typedef long long ll;

#define MAX_N 200000
#define MAX_M 100000
#define MAX_V 100
#define MAX_E 100
#define MAX_Q 100000

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

int ddx[] = {-1, 0, 1, 0, -1, 1, -1, 1};
int ddy[] = {0, -1, 0, 1, 1, 1, -1, -1};

string as = {"ABCDEFGHIJKLMNOPQRSTUVWXYZ"};
string ab = {"abcdefghijklmnopqrstuvwxyz"};

ll gcd(ll x, ll y) {
  if(y==0) return x;
  else return gcd(y, x%y);
}

ll lcm(ll x, ll y) {
  return (x*y)/gcd(x, y);
}

void yes() {
  cout << "Yes" << endl;
}

void no() {
  cout << "No" << endl;
}

void print_array(int array[], int len) {

  for(int i=0; i<len; ++i) {
    cout << array[i] << endl;
  }

}

ll absolute(ll x) {
  return (x<0)? (-1)*x : x;
}

//g++ AtCoder.cpp -o AtCoder
//AtCoder

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



int main() {

  int r;
  cin >> r;
  cout << 3*r*r << endl;

  return 0;
}


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

#define forn(i, n) for(int i = 0; i < (int)(n); ++i)
#define for1(i, n) for(int i = 1; i <= (int)(n); ++i)
#define fore(i, a, b) for(int i = (int)(a); i <= (int)(b); ++i)
#define ford(i, n) for(int i = (int)(n) - 1; i >= 0; --i)
#define ford1(i, n) for(int i = (int)(n); i>=1; --i)
#define fored(i, a, b) for(int i = (int)(b); i >= (int)(a); --i)
#define sz(v) ((int)((v).size()))
#define all(v) (v).begin(), (v).end()
#define clr(v) memset(v, 0, sizeof(v))
#define clr1(v) memset(v, 0xFF, sizeof(v))
#define mp make_pair
#define pb push_back
#define fi first
#define se second

using namespace std;

typedef pair<int, int> pii;
typedef vector<pii> vpi;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef long long i64;
typedef unsigned long long u64;
typedef long double ld;
typedef vector<ld> vld;

typedef vector<i64> vi64;

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

void solve() {
  int n;
  cin >> n;
  vi a(n * 2);
  forn(i, n * 2) cin >> a[i];
  sort(all(a));
  int s = 0;
  forn(i, n) s += a[i * 2];
  cout << s << '\n';
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << fixed; cout.precision(15);
  cerr << fixed; cerr.precision(15);
#ifdef HOME
  freopen("input.txt", "r", stdin);
#endif
  solve();
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
using namespace std;
int main()
{
	long long w, h, x, y;
	cin >> w >> h >> x >> y;
	cout << fixed;
	cout << setprecision(9);
	cout << w*h/2.0 << " ";
	cout << ((w==x*2 && h==y*2)?1:0);
	
}

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

int main() {
	string s;
	cin >> s;
	if((s[0] == s[1] && s[1]== s[2]) || (s[1] == s[2]&& s[2] == s[3])) cout << "Yes" << endl;
	else cout << "No" << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define Q (400001*2)

int main(){
	int *A=(int*)malloc(sizeof(int)*Q);
	int start=(Q/2);
	int end=start;

	int N;
	int command,d,p,x;

	scanf("%d",&N);
	for(int i=0;i<N;i++){
		scanf("%d",&command);
		switch(command){
		case 0:
			scanf("%d %d",&d,&x);
			if(start==end){//最初
				A[start]=x;
				start--;
				end++;
			}else{
				if(d==0){
					A[start]=x;
					start--;
				}else{
					A[end]=x;
					end++;
				}
			}
			break;
		case 1:
			scanf("%d",&p);
			printf("%d\n",A[start+p+1]);
			break;
		case 2:
			scanf("%d",&d);
			if(d==0){
				start++;
			}else{
				end--;
			}
			break;
		}
		/*printf("A:");
		for(int i=start+1;i<end;i++){
			printf("%d,",A[i]);
		}printf("\n");*/
	}

	return 0;
}


Measured memory_bytes: 3356
#include <bits/stdc++.h>
using namespace std;
inline void read (int &x) {
	char ch = getchar(); int f = 0; x = 0;
	while (!isdigit(ch)) {if (ch == '-') f = 1; ch = getchar();}
	while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
	if (f) x = -x;
}
const int N = 1e5 + 10, mod = 1e9 + 7;
int n, m, a[N], sa[N], sb[N], fac[N], inv[N];
inline int Pow (int x, int a) {
	int res (1);
	while (a) {
		if (a & 1) res = 1ll * res * x % mod;
		x = 1ll * x * x % mod, a >>= 1;
	} return res;
}
inline int C (int a, int b) {
	return 1ll * fac[a] * inv[b] % mod * inv[a - b] % mod;
}
signed main() {
	read (n), read (m);
	for (int i = 1; i <= n; ++i) read (a[i]);
	sort (a + 1, a + n + 1);
	fac[0] = inv[0] = fac[1] = inv[1] = 1;
	for (int i = 2; i <= n; ++i) fac[i] = 1ll * fac[i - 1] * i % mod, inv[i] = Pow (fac[i], mod - 2);
	int res1 (0), res2 (0);
	for (int i = 1; i + m - 1 <= n; ++i)
		res1 = (res1 + 1ll * C (n - i, m - 1) * a[i] % mod) % mod;
	for (int i = n; i >= m; --i)
		res2 = (res2 + 1ll * C (i - 1, m - 1) * a[i] % mod) % mod;
//	printf ("%d %d\n", res1, res2);
	printf ("%d\n", ((res2 - res1) % mod + mod) % mod);
	return 0;
}

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

#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
#define REP(i, n) for(int i = 0;i < n;++i)
#define REPR(i, n) for(int i = n;i >= 0;--i)
#define FOR(i, a, b) for(int i = a;i < b;++i)
#define ALL(x) (x).begin(),(x).end()
#define INF 999999999
using namespace std;
#define lint long long

int main()
{
  int N;
  int out = 0;
  cin >> N;
  vector<int> X(N);
  REP(i,N){
   cin >> X[i]; 
  }
  int sum = 0;
  REP(i,N){
   sum += X[i]; 
  }
  int count = 1;
  int P = round((double)sum/N);
  REP(i,N){
  	out += pow(X[i] - P ,2);
  }
  cout << out;
  return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys

WHITE, GRAY, BLACK = 0, 1, 2
D_MAX = int(1e7 + 1)


def generate_adj_matrix(v_info):
    for v_detail in v_info:
        v_index = int(v_detail[0])
        v_adj_length = int(v_detail[1])
        v_adj_list = v_detail[2:]
        # assert len(v_adj_list) == v_adj_length * 2
        for j in range(0, v_adj_length * 2, 2):
            init_adj_matrix[v_index][v_adj_list[j]] = int(v_adj_list[j + 1])

    return init_adj_matrix


def dijkstra_path():
    path_list[0] = 0

    while True:
        min_cost = D_MAX
        current_vertex = None
        for i in range(vertices_num):
            if color[i] is not BLACK and path_list[i] < min_cost:
                min_cost = path_list[i]
                current_vertex = i

        if min_cost == D_MAX:
            break

        color[current_vertex] = BLACK

        for v in range(vertices_num):
            current_v_weight = adj_matrix[current_vertex].get(str(v), -1)
            if current_v_weight < 0:
                continue
            elif color[v] is not BLACK:
                if path_list[current_vertex] + current_v_weight < path_list[v]:
                    path_list[v] = path_list[current_vertex] + current_v_weight
                    parent_list[v] = current_vertex
                    color[v] = GRAY

    return path_list


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices_num = int(_input[0])
    init_vertices_table = list(map(lambda x: x.split(), _input[1:]))
    # assert len(init_vertices_table) == vertices_num

    parent_list, path_list = [-1] * vertices_num, [D_MAX] * vertices_num
    color = [WHITE] * vertices_num
    init_adj_matrix = [{} for _ in range(vertices_num)]
    adj_matrix = generate_adj_matrix(init_vertices_table)
    ans = dijkstra_path()
    for j in range(vertices_num):
        print(j, ans[j])

Measured memory_bytes: 8776
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<string>
#include<vector>
using namespace std;
const int mod = 1000000007;
#define ll long long

int main()
{
	int a[5], k;
	for (int i = 0; i < 5; i++) cin >> a[i];
	cin >> k;
	for (int i = 0; i < 5; i++) {
		for (int j = i + 1; j < 5; j++) {
			if (a[j] - a[i] > k) {
				cout << ":(" << endl;
				return 0;
			}
		}
	}
	cout << "Yay!" << endl;
}

Measured memory_bytes: 256
object Main extends App {
  val sc = new java.util.Scanner(System.in)
  val n, m, c = sc.nextInt
  val bs = Array.fill(m)(sc.nextInt)
  val as = Array.fill[Int](n, m)(sc.nextInt)
  println(as.count(_.zip(bs).map(tpl => tpl._1 * tpl._2).sum + c > 0))
}

Measured memory_bytes: 25808
#include <iostream>
#include <map>
#include <algorithm>
#include <string>
#include <vector> 
#include <numeric>
#include <cmath>
#include <queue>


#define CHMAX(a,b) a = std::max(a,b)
#define CHMIN(a,b) a = std::min(a,b)
#define CHABS(a) a = std::abs(a) 
#define COUT(a) std::cout << a << std::endl
#define CERR(a) std::cerr << a << std::endl
#define FOR(n) for(lli i = 0; i < n; i++)

using namespace std;
using lli = long long int;
using pll = pair<lli, lli>;
using tlll = tuple<lli, lli, lli>;

lli mod197 = 1000000007LL;

// ax + by = gcd(a,b) 最大公約数
template< typename T >
T extgcd(T a, T b, T& x, T& y) {
	T d = a;
	if (b != 0) {
		d = extgcd(b, a % b, y, x);
		y -= (a / b) * x;
	}
	else {
		x = 1;
		y = 0;
	}
	return d;
}

int main(void) {

  double a,b;
  cin>>a>>b;
  COUT(a/b);
  
	return 0;
}


Measured memory_bytes: 256
n = int(input())
csf = [tuple(map(int, input().split())) for _ in range(n - 1)]#csf
for i in range(n):
    #i:起点
    t = 0#駅jの出発時刻, 駅n（添え字n - 1）では、この時刻がprintされるので、初期値は0とする
    for j in range(i, n - 1):
        #j:乗車する区間
        c_j, s_j, f_j = csf[j]

        #駅jの出発時刻を求める
        if t < s_j:
            t = s_j
        elif t % f_j == 0:
            pass
            #t = t
        else:
            #始発より後に駅に到着し、駅で電車を待つ
            t += f_j - (t % f_j)
        t += c_j#乗車して次の駅に到着させる
    print(t)#駅n（添え字n - 1）の到着時刻

Measured memory_bytes: 3188
#![allow(unused_imports)]
#![allow(non_snake_case)]
use proconio::{input, fastout};
use proconio::marker::{Chars, Bytes, Usize1};

#[fastout]
fn main() {
    input!{
        n:usize, x:usize, t:usize
    }
    println!("{}", t * ((n - 1) / x + 1));
}


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

int main()
{
	int N;
	cin >> N;
	bool f = false;
	for (int i = 0; i < N / 7 + 1; i++) {
		if ((N - 7 * i) % 4 == 0) {
			f = true;
		}
	}
	if (f) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
}

Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

ans = 0
for i in range(N):
    m = min(A[i], B[i])
    ans += m
    A[i] -= m
    B[i] -= m
    m2 = min(A[i+1], B[i])
    ans += m2
    A[i+1] -= m2
    B[i] -= m2

print(ans)

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

#define NDEBUG
#ifdef DEBUG
#include "cout11.h"
#undef NDEBUG
#endif
#include <cassert>

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> ii;
typedef pair<ll,ll> llll;
typedef pair<double,double> dd;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<ll> vll;

#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);++var)
#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define ALL(c)  (c).begin(),(c).end()
#define RALL(c)  (c).rbegin(),(c).rend()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())
#define mset(arr,val)  memset(arr,val,sizeof(arr))
#define mid(x,y) ((x)+((y)-(x))/2)
#define IN(x,a,b) ((a)<=(x)&&(x)<=(b))

int solve(ll x, ll y) {
    int c=0;
    while (y>=x) { ++c; y>>=1; }
    return c;
}

int main() {
    ll x,y; cin >>x>>y;
    cout << solve(x,y) << endl;
    return 0;
}


Measured memory_bytes: 256
import heapq
N = int(input())
edges = [[] for _ in range(N)]
for i in range(N-1):
    a, b, c = map(int, input().split())
    edges[a-1].append([b-1, c])
    edges[b-1].append([a-1, c])
Q, K = map(int, input().split())
K -= 1


ans_list = []
def dijkstra(edges, num_v, start):
    dist = [float('inf')] * num_v
    dist[start] = 0
    q = []
    heapq.heappush(q, [0, start])

    while len(q) > 0:
        _, u = heapq.heappop(q)
        for edge in edges[u]:
            if dist[edge[0]] > dist[u] + edge[1]:
                dist[edge[0]] = dist[u] + edge[1]
                heapq.heappush(q, [dist[u] + edge[1], edge[0]])
    return dist
base = dijkstra(edges,  N, K)
for i in range(Q):
    x, y = map(lambda n: int(n) - 1, input().split())
    x_K = base[x]
    K_y = base[y]
    ans_list.append(x_K + K_y)

for i in ans_list:
    print(i)

Measured memory_bytes: 58396
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const ll INF=1LL<<60;
int main(){
    int n;cin >> n;
    vector<vector<string>> ans(n);
    ans[0].push_back("a");
    for(int x=1;x<n;x++){
        for(string t:ans[x-1]){
            int m=0;
            for(int i=0;i<t.size();i++){
                chmax(m,t[i]-'a');
            }
            for(int i=0;i<=m+1;i++){
                ans[x].push_back(t+char('a'+i));
            }
        }
    }
    sort(ans[n-1].begin(),ans[n-1].end());
    for(string t:ans[n-1]){
        cout << t << endl;
    }
}


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

namespace test
{
    class Program
    {
        static void Main(string[] args)
        {
            var input = ReadArrayInt();
            var R = input[0];
            var G = input[1];
            var B = input[2];
            var N = input[3];
            var ans = 0;
            for (int i = 0; i <= N / R; i++)
            {
                for (int j = 0; j <= (N - R * i) / G; j++)
                {
                    if ((N - R * i - G * j) % B == 0) ans++;
                }
            }

            Console.WriteLine(ans);
            Console.ReadLine();
        }

        static string Read() { return Console.ReadLine(); }
        static int ReadInt() { return int.Parse(Read()); }
        static long ReadLong() { return long.Parse(Read()); }
        static int[] ReadArrayInt() { return Read().Split(' ').Select(s => int.Parse(s)).ToArray(); }
        static long[] ReadArrayLong() { return Read().Split(' ').Select(s => long.Parse(s)).ToArray(); }
    }
}

Measured memory_bytes: 11348
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,i,x,y,sum=0;
    cin>>n;
    int arr[n];
    for (i=0;i<n;i++)
    {
        cin>>arr[i];
        sum+=arr[i];
    }
    x= *max_element(arr,arr+n);
    y= sum-x;
    if (x<y)
        cout<<"Yes"<<endl;
    else 
        cout<<"No"<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
#define MAX 101
 
int arr[MAX], W;
 
void ins(int id, int w){
    for(int i = 0 ; i < W-w+1 ; i++){
	if(arr[i] == -1){
	    bool flg = true;
	    for(int j = i ; j < i+w ; j++){
		if(arr[j] != -1){
		    flg = false;
		    break;
		}
	    }
 
	    if(flg){
		cout << i << endl;
		for(int j = i ; j < i+w ; j++){
		    arr[j] = id;
		}
		return;
	    }
	}
    }
 
    cout << "impossible" << endl;
}
 
void del(int id){
    for(int i = 0 ; i < W ; i++){
	if(arr[i] == id){
	    while(arr[i] == id){
		arr[i++] = -1;
	    }
	    return;
	}
    }
}
 
int main(){
    int Q, id, w;
    char ch;
 
    while(cin >> W >> Q ,(W | Q)){
	memset(arr,-1,sizeof(arr));
	for(int i = 0 ; i < Q ; i++){
	    cin >> ch;
 
	    if(ch == 's'){
		cin >> id >> w;
		ins(id, w);
	    }else{
		cin >> id;
		del(id);
	    }
	}
	cout << "END" << endl;
    }
    return 0;
}

Measured memory_bytes: 3084
#include <bits/stdc++.h>
using namespace std;
#define int long long 

signed main()
{
  int N;
  int A, B, C, D;
  int ansa, ansb, ansc, ansd;
  int minv;
  bool flag = false;
  while(cin >> N, N) {
    if(flag) cout << endl;
    flag = true;

    minv = 1LL << 60;
    
    cin >> A >> B >> C >> D;
    
    for(int i = 0; i <= A; i++) {
      for(int j = 0; j <= B; j++) {
	for(int k = 0; k <= C; k++) {
	  for(int l = 0; l <= D; l++) {
	    int val = i * 10 + j * 50 + k * 100 + l * 500 - N;
	    
	    if(val < 0) continue;
	    
	    int a, b, c, d;
	    
	    d = val / 500, val -= d * 500;
	    c = val / 100, val -= c * 100;
	    b = val / 50, val -= b * 50;
	    a = val / 10, val -= a * 10;
	    if(i && a || j && b || k && c || l && d) continue;
	    int v = a + b + c + d + A - i + B - j + C - k + D - l;
	    if(minv > v) {
	      minv = v;
	      ansa = i, ansb = j, ansc = k, ansd = l;
	    }
	    
	  }
	}
      }
    }

    if(ansa) cout << 10 << " " << ansa << endl;
    if(ansb) cout << 50 << " " << ansb << endl;
    if(ansc) cout << 100 << " " << ansc << endl;
    if(ansd) cout << 500 << " " << ansd << endl;
  }

  return 0;
}
	    
	    
	    

Measured memory_bytes: 3056
#define NDEBUG
NDEBUG


#include <algorithm>
#include <cassert>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <memory>
#include <random>

#define FOR(i, n) for (int i = 0; i < (n); ++i)


typedef int64_t int64;


using namespace std;

// TC_REMOVE_BEGIN
/// caide keep
bool __hack = std::ios::sync_with_stdio(false);
/// caide keep
auto __hack1 = cin.tie(nullptr);
// TC_REMOVE_END


namespace template_util {
    

    constexpr int bytecount(uint64_t x) {
        return x ? 1 + bytecount(x >> 8) : 0;
    }

    /// caide keep
    template<int N>
    struct bytetype {
        
    };

    /// caide keep
    template<>
    struct bytetype<4> {
        
    };

    /// caide keep
    template<>
    struct bytetype<3> {
        
    };

    /// caide keep
    template<>
    struct bytetype<2> {
        
    };

    /// caide keep
    template<>
    struct bytetype<1> {
        
    };

    /// caide keep
    template<>
    struct bytetype<0> {
        
    };

    /// caide keep
    template<uint64_t N>
    struct minimal_uint : bytetype<bytecount(N)> {
    };
}


template<class T>
T next(istream& in) {
    T ret;
    in >> ret;
    return ret;
}


void solve(istream& in, ostream& out) {
    int n = next<int>(in);
    int T = next<int>(in);
    int64 res = 0;
    int stops = T;
    int tprev = next<int>(in);
    FOR(i, n) if (i) {
            int t = next<int>(in);
            if (t > stops) {
                res += (stops - tprev);
                tprev = t;
                stops = t + T;
            } else {
                stops = t + T;
            }
        }
    res += (stops - tprev);
    out << res << endl;
}


int main() {
    solve(cin, cout);
    return 0;
}



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

int main(int argc, char const *argv[])
{
    int abc[5];

    for (int i = 0; i < 5; i++)
    {
        cin >> abc[i];
    }

    int last = 0;
    for (int i = 0; i < 5; i++)
    {
        int tmp = 10 - abc[i] % 10;
        if (tmp != 10 && tmp > last)
        {
            last = tmp;
        }
    }

    int ans = 0;
    for (int i = 0; i < 5; i++)
    {
        ans += (int)((double)abc[i] / 10.0 + 0.9);
    }
    ans *= 10;

    ans -= last;

    cout << ans << "\n";

    return 0;
}

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

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define test() int t;cin>>t;for(int test=1;test<=t;test++)
#define pb push_back
#define nl cout<<"\n"
#define F first
#define S second
#define all(x) x.begin(),x.end()

template<class C> void min_self( C &a, C b ){ a = min(a,b); }
template<class C> void max_self( C &a, C b ){ a = max(a,b); }

const ll MOD = 1000000007;
ll mod( ll n, ll m=MOD ){ n%=m,n+=m,n%=m;return n; }

const int MAXN = 1e5+5;
const int LOGN = 21;
const ll INF = 1e14;
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};

int main() 
{
    fastio();

    int h,a;
    cin>>h>>a;

    int ans = (h+a-1)/a;
    cout<<ans,nl;


    cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}

Measured memory_bytes: 256
#0219
while True:
    n = int(input())
    if n == 0:
        break
    c = [int(input()) for c in range(n)]
    for i in range(10):
        x = c.count(i)
        for j in range(x):
            print('*',end='')
        if x == 0:
            print('-',end='')
        print()


Measured memory_bytes: 7684
n = int(input())
for i in range(1, n+1):
    if i % 3 == 0:
        print(" {}".format(i), end = "")
    else:
        x = i 
        while x:
            if x % 10 == 3:
                print(" {}".format(i), end = "")
                break
            x //= 10
print()


Measured memory_bytes: 5872
//2018.09.23

#include <iostream>
using namespace std;

int main() {

    int a,b,c;
    cin >> a >> b >> c;

    int maxv,midv,minv;
    maxv = max(max(a,b),c);
    minv = min(min(a,b),c);

    if(a>b){
        if(b>=c) midv = b;
        else{
            if(a>=c) midv = c;
            else midv = a;
        }
    }
    else if(a==b){
        midv=a;
    }
    else{
        if(a>=c) midv = a;
        else{
            if(b>=c) midv = c;
            else midv = b;
        }
    }


  cout << maxv*10+midv+minv <<endl;

    return 0;
}


Measured memory_bytes: 256
object Main extends App {
  val sc = new java.util.Scanner(System.in)
  val Q, H, S, D, N = sc.nextLong()
  val oneLiterPrice = Seq(4 * Q, 2 * H, S).min
  val twoLiterPrice = (oneLiterPrice * 2) min D
  println((N / 2) * twoLiterPrice + (N % 2) * oneLiterPrice)
}


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

using namespace std;
typedef long long ll;

#define rep(i, n) for (ll i = 0; i < (n); ++i)
//#define rep(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) ll(x.size())
//typedef pair<int, int> P;
typedef pair<ll, ll> P;
//const double INF = 1e10;
//const ll INF = LONG_LONG_MAX;
const ll MINF = LONG_LONG_MIN;
const int INF = INT_MAX;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)

bool contain(set<int> &s, int a) { return s.find(a) != s.end(); }


//ifstream myfile("C:\\Users\\riku\\Downloads\\0_00.txt");
//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);

typedef priority_queue<ll, vector<ll>, greater<ll>> PQ_ASK;
const int mod = 1000000007;

int main() {

    int a, b, c, d;
    cin >> a >> b >> c >> d;

    cout << max(a * b, c * d) << endl;

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
int ans;
string s, t;
int main(){
	cin >> s >> t;
	rep(i,3) if(s[i] == t[i]) ans++;
	printf("%d\n", ans);
}

Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i = 0; i < (N); i++)
#define repo(i,N) for(int i = 1; i < (N); i++)
//#define int long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
//#define num 1000000007
#define pi acos(-1.0)
//cout << fixed << setprecision (10);   小数点以下１０桁まで
//intの最大値2147483647 ≒ 2×10^9
//long longの最大値9223372036854775807 ≒ 9×10^18
//'大文字'+=32;    で小文字に
//string s = to_string(int数);
//int n = stoi(string文字列);

int main() {
  int a,b;
  cin >>a>>b;
  
  int x = 0;
  int ans = 0;
  rep(i,a) {
  int l;
  cin >> l;
  x+=l;
    if (x<=b) ans++;
  } 
  
  cout << ans+1 << endl;
  
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(ri,n) for(int ri = (int)(n-1); ri >= 0; ri--)
#define rep2(i,x,n) for(int i = (int)(x); i < (int)(n); i++)
#define rrep2(ri,x,n) for(int ri = (int)(n-1); ri >= (int)(x); ri--)
#define repit(itr,x) for(auto itr = x.begin(); itr != x.end(); itr++)
#define rrepit(ritr,x) for(auto ritr = x.rbegin(); ritr != x.rend(); ritr++)
#define ALL(x) x.begin(), x.end()
using ll = long long;
using namespace std;

int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i, n) cin >> a.at(i);
  vector<int> b(n);
  rep(i, n) cin >> b.at(i);
  vector<int> c(n-1);
  rep(i, n-1) cin >> c.at(i);
  ll ans = 0;
  rep(i, n){
    ans += b.at(a.at(i)-1);
    if(i > 0){
      if(a.at(i) == a.at(i-1)+1){
        ans += c.at(a.at(i)-2);
      }
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3592
# -*- coding: utf-8 -*-

n, k = map(int,input().split())
r, s, p = map(int,input().split())
t = input()
win = {"r":2,"s":0,"p":1}
not_win = {"r":[0,1], "s":[1,2], "p":[0,2]}
not_win_i = {0:[1,2], 1:[0,2], 2:[0,1]}
point = {"r":p,"s":r,"p":s}

ans = 0
for i in range(k):
    plays = []
    for a in range(int(n/k)+1):
        if a*k+i < n:
            plays.append(a*k+i)
    #print(plays)
    dp = [[0] * 3 for _ in range(len(plays))]

    for j, play in enumerate(plays):
        if j == 0:
            f_play = t[plays[0]]
            dp[j][win[f_play]] += point[f_play]
        else:
            n_play = t[play]
            n0 = not_win[n_play][0]
            n1 = not_win[n_play][1]
            dp[j][win[n_play]] = max(dp[j-1][n0], dp[j-1][n1]) + point[n_play]
            dp[j][n0] = max(dp[j-1][not_win_i[n0][0]], dp[j-1][not_win_i[n0][1]])
            dp[j][n1] = max(dp[j-1][not_win_i[n1][0]], dp[j-1][not_win_i[n1][1]])
    #print(dp)
    ans += max(dp[-1])
print(ans)


Measured memory_bytes: 20244
#include<stdio.h>

int solve(int a,int b,int c){
	if(a==1&&b>=c&&b<10){
		return 1;
	}
	if(a==1)return 0;
	int ret=0;
	for(int i=c;i<10&&i<b;i++){
		ret+=solve(a-1,b-i,i+1);
	}
	return ret;
}
int main(){
	int a,b;
	while(1){
		scanf("%d%d",&a,&b);
		if(a==0)return 0;
		printf("%d\n",solve(a,b,0));
	}
}

Measured memory_bytes: 0
from heapq import heappush,heappop
dataX=[]
dataY=[]
mae=dict()
ushiro=dict()
N=int(input())
A=list(map(int,input().split()))
X=A[0:N]
Y=A[N:2*N]
Z=A[2*N:3*N]
for i in range(N):
    heappush(dataX,X[i])
    heappush(dataY,-1*Z[i])
mae[0]=sum(X)
ushiro[0]=-1*sum(Z)
for i in range(1,N+1):
    mae[i]=mae[i-1]+Y[i-1]
    heappush(dataX,Y[i-1])
    mae[i]-=heappop(dataX)
    ushiro[i]=ushiro[i-1]-Y[N-i]
    heappush(dataY,-1*Y[N-i])
    ushiro[i]-=heappop(dataY)
ans=-1*float('inf')
for i in range(N+1):
    ans=max(ans,mae[i]+ushiro[N-i])
print(ans)

Measured memory_bytes: 51924
#! /usr/bin/env python3

h, w = map(int, input().split())

m = []
for i in range(h):
    m.append(input())

res = True

for r in range(h):

    for c in range(w):
        if m[r][c] == ".": continue
        if c > 0 and m[r][c-1] == "#":
            continue
        if c < w-1 and m[r][c+1] == "#":
            continue
        if r > 0 and m[r-1][c] == "#":
            continue
        if r < h-1 and m[r+1][c] == "#":
            continue
        res = False

if res == True:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 3064
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>

int main(void){

    int A, B, C;

    scanf("%d%d%d", &A, &B, &C);

    if(A + B >= C){
        printf("Yes\n");
    }else{
        printf("No\n");
    }

    return 0;
}

Measured memory_bytes: 1632
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> P;
int INF = 1e9+7;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
signed main() {
    int N;
    cin >> N;
    vector<int>A(N);
    vector<int>cnt(N+1);
    for(int i = 0; i < N; i++) {
        cin >> A[i];
        cnt[i+1] += A[i];
    }
    for(int i = 0; i < N; i++) {
        cnt[i+1]+=cnt[i];
    }
    sort(cnt.begin(),cnt.end());
    int ans = 0;
    int sum = 1;
    for(int i = 1; i <= N; i++) {
        if(cnt[i] == cnt[i-1]) {
            sum++;
        }
        else {
            ans+=(sum*(sum-1))/2;
            sum = 1;
        }
    }
    if(sum != 1) {
        ans+=(sum*(sum-1))/2;
    }
    cout << ans << endl;
}


Measured memory_bytes: 6312
# include <bits/stdc++.h>
using namespace std;
namespace Base{
	# define mr make_pair
	typedef long long ll;
	typedef double db;
	const int inf = 0x3f3f3f3f, INF = 0x7fffffff;
	const ll  infll = 0x3f3f3f3f3f3f3f3fll, INFll = 0x7fffffffffffffffll;
	template<typename T> void read(T &x){
    	x = 0; int fh = 1; double num = 1.0; char ch = getchar();
		while (!isdigit(ch)){ if (ch == '-') fh = -1; ch = getchar(); }
		while (isdigit(ch)){ x = x * 10 + ch - '0'; ch = getchar(); }
	    if (ch == '.'){
	    	ch = getchar();
	    	while (isdigit(ch)){num /= 10; x = x + num * (ch - '0'); ch = getchar();}
		}
		x = x * fh;
	}
	template<typename T> void chmax(T &x, T y){x = x < y ? y : x;}
	template<typename T> void chmin(T &x, T y){x = x > y ? y : x;}
}
using namespace Base;

const int N = 100010, M = 200010, P = 1e9 + 7;
priority_queue <pair<ll, int> > hp;
struct Edge{
	int data, next, vote;
}e[M * 2];
int head[N], place, p[N], f[N], g[N], ans;
ll dis[N];
void build(int u, int v, int w){
	e[++place].data = v; e[place].next = head[u]; head[u] = place; e[place].vote = w;
}
int n, m, S, T;
void dij(){
	memset(dis, inf, sizeof(dis));
	hp.push(mr(0, S));
	while (hp.size() != 0){
		while (hp.size() > 0 && dis[hp.top().second] != dis[0]) hp.pop();
		if (hp.size() == 0) break;
		int x = hp.top().second;
		dis[x] = -hp.top().first;
		for (int ed = head[x]; ed != 0; ed = e[ed].next)
			if (dis[e[ed].data] == dis[0]) hp.push(mr(-(dis[x] + e[ed].vote), e[ed].data));
	}
}
bool cmp(int x, int y){
	return dis[x] < dis[y];
}
int main(){
	read(n); read(m);
	read(S); read(T);
	for (int i = 1; i <= m; i++){
		int u, v, w; 
		read(u); read(v); read(w);
		build(u, v, w); build(v, u, w);
	}
	dij();
	for (int i = 1; i <= n; i++) p[i] = i;
	sort(p + 1, p + n + 1, cmp);
	f[S] = 1;
	for (int i = 1; i <= n; i++){
		int x = p[i];
		for (int ed = head[x]; ed != 0; ed = e[ed].next)
			if (dis[e[ed].data] == dis[x] + e[ed].vote)
				f[e[ed].data] = (f[e[ed].data] + f[x]) % P;
	}
	g[T] = 1;
	for (int i = 1; i <= n; i++){
		int x = p[n - i + 1];
		for (int ed = head[x]; ed != 0; ed = e[ed].next)
			if (dis[e[ed].data] == dis[x] - e[ed].vote)
				g[e[ed].data] = (g[e[ed].data] + g[x]) % P;
	}
	ans = 1ll * f[T] * f[T] % P;
	for (int i = 1; i <= n; i++){
		int x = i;
		for (int ed = head[x]; ed != 0; ed = e[ed].next)
			if (dis[e[ed].data] == dis[x] + e[ed].vote){
				ll tmp = dis[T] - dis[e[ed].data];
				if (tmp < dis[e[ed].data] && tmp > dis[x] - (dis[e[ed].data] - dis[x]))
					ans = ((ans - 1ll * f[x] * g[e[ed].data] % P * f[x] % P * g[e[ed].data]) % P + P) % P;
			}
	}
	for (int i = 1; i <= n; i++)
		if (dis[i] == dis[T] - dis[i])
		ans = ((ans - 1ll * f[i] * g[i] % P * f[i] % P * g[i]) % P + P) % P;
	printf("%d\n", ans);
	return 0;
}



Measured memory_bytes: 9200
#include <stdarg.h>
#include <stdio.h>

long long max(int len, ...) {
    long long i, _max, num;
    va_list ap;
    va_start(ap, len);

    _max = va_arg(ap, long long);
    for (i = 1; i < len; i++) {
        num = va_arg(ap, long long);
        if (num > _max)
            _max = num;
    }
    va_end(ap);
    return _max;
}
long long min(int len, ...) {
    long long i, _min, num;
    va_list ap;
    va_start(ap, len);

    _min = va_arg(ap, long long);
    for (i = 1; i < len; i++) {
        num = va_arg(ap, long long);
        if (num < _min)
            _min = num;
    }
    va_end(ap);
    return _min;
}

int main(void) {
    int i, j, N, v[110];
    long long MAXW, w[110], dp[110][100010];
    scanf("%d%lld", &N, &MAXW);
    for (i=1;i<=N;i++) {
        scanf("%lld%d", &w[i], &v[i]);
    }

    for (i=0;i<=N;i++) {
        for (j=0;j<=100000;j++) {
            dp[i][j] = 1LL<<60;
        }
    }
    dp[1][v[1]] = w[1];
    for (i=2;i<=N;i++) {
        dp[i][v[i]] = w[i];
        for (j=0;j<=100000;j++) {
            if (j-v[i] >= 0) {
                dp[i][j] = min( 3, dp[i-1][j-v[i]] + w[i], dp[i-1][j], dp[i][j] );
            } else dp[i][j] = min( 2, dp[i-1][j], dp[i][j] );
        }
    }

    for (j=100000;j>0;j--) {
        if (dp[N][j] <= MAXW) {
            printf("%lld\n", j);
            break;
        }
    }
    return 0;
}

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    ll n;
    cin >> n;
    
    vector<ll> a(n);
    rep(i,n) cin >> a[i];
    
    ll cnt = 1;
    
    for(int i = 0; i < n - 1; i++){
        if(a[i] < a[i+1]){
            int j = 1;
            while(i+j < n - 1){
                if(a[i+j] <= a[i+j+1]) j++;
                else {
                    cnt++;
                    i+=j;
                    break;
                }
            }
            if(i + j >= n - 1) break;
        }
        
       else if(a[i] > a[i+1]){
            int j = 1;
            while(i+j < n - 1){
                if(a[i+j] >= a[i+j+1]) j++;
                else {
                    cnt++;
                    i+=j;
                    break;
                }
            }
           if(i + j >= n - 1) break;
        }
    }
    
    cout << cnt << endl;
    
}


Measured memory_bytes: 1024
# vim: set fileencoding=utf-8:


def main():
    N = input()
    V = map(int, input().split())
    C = map(int, input().split())
    VCdiff = [v - c for v, c in zip(V, C)]
    a = filter(lambda x: 0 <= x, VCdiff)
    print(sum(list(a)))


if __name__ == "__main__":
    main()


Measured memory_bytes: 3060