QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#135416#6310. Dining ProfessorsSpinozaAC ✓26ms17276kbC++208.5kb2023-08-05 14:59:232023-08-05 14:59:26

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-05 14:59:26]
  • 评测
  • 测评结果:AC
  • 用时:26ms
  • 内存:17276kb
  • [2023-08-05 14:59:23]
  • 提交

answer

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<climits>
#include<cctype>
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
using vl=vector<ll>;
using vc=vector<char>;
using vvl=vector<vl>;
using vvc=vector<vc>;
using pll=pair<ll,ll>;
using mll=map<ll,ll>;
using sl=set<ll>;
using ql=queue<ll>;
using pql=priority_queue<ll> ;
using stl=stack<ll>;
constexpr double eps=1e-10;
constexpr ll inf=1e18;
constexpr ll N=1<<20;
constexpr ll P=1e9+7;
constexpr ll inv2=(P+1)/2;
#define pb(x) push_back(x)
#define forfront(i,x,y) for (ll i = (x) ; i <= (y) ; ++i)
#define forback(i,x,y) for (ll i = (x) ; i >=(y) ; --i )
#define add(a,b) ( a + b >= P ? a + b - P : a + b )
#define dec(a,b) ( a < b ? a - b + P : a - b )
#define sz(v) ( (ll) v . size ( ) )
#define all(v) (v).begin (), (v).end ()
#define one(x) memset (x , -1 , sz (x) )
#define zero(x) memset ( x, 0 , sz (x) )
#define LOCAL
namespace Spinoza{
	namespace IO{
		#ifndef LOCAL
			constexpr auto maxn=1<<20;
			char in[maxn],out[maxn],*p1=in,*p2=in,*p3=out;
			#define getchar() (p1==p2&&(p2=(p1=in)+fread(in,1,maxn,stdin),p1==p2)?EOF:*p1++)
			#define flush() (fwrite(out,1,p3-out,stdout))
			#define putchar(x) (p3==out+maxn&&(flush(),p3=out),*p3++=(x))
			class Flush{public:~Flush(){flush();}}_;
		#endif
		namespace usr{
			template<typename type>
			inline type read(type &x){
				x=0;bool flag(0);char ch=getchar();
				while(!isdigit(ch)) flag^=ch=='-',ch=getchar();
				while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
				return flag?x=-x:x;}
			template<typename type>
			inline void write(type x){
				x<0?x=-x,putchar('-'):0;
				static short Stack[50],top(0);
				do Stack[++top]=x%10,x/=10;while(x);
				while(top) putchar(Stack[top--]|48);}
			inline char read(char &x){do x=getchar();while(isspace(x));return x;}
			inline char write(const char &x){return putchar(x);}
			inline void read(char *x){static char ch;read(ch);do *(x++)=ch;while(!isspace(ch=getchar())&&~ch);}
			template<typename type>inline void write(type *x){while(*x)putchar(*(x++));}
			inline void read(string &x){static char ch;read(ch),x.clear();do x+=ch;while(!isspace(ch=getchar())&&~ch);}
			inline void write(const string &x){for(int i=0,len=x.length();i<len;++i)putchar(x[i]);}
			template<typename type,typename...T>inline void read(type &x,T&...y){read(x),read(y...);}
			template<typename type,typename...T>
			inline void write(const type &x,const T&...y){write(x),putchar(' '),write(y...),sizeof...(y)^1?0:putchar('\n');}
			template<typename type>
			inline void put(const type &x,bool flag=1){write(x),flag?putchar('\n'):putchar(' ');}}
		#ifndef LOCAL
			#undef getchar
			#undef flush
			#undef putchar
		#endif
	}using namespace IO::usr;
}using namespace Spinoza::IO::usr;
template<class T>
constexpr T qpow(T a, ll b) {T res = 1;for (; b; b /= 2, a = a * a %P) {if (b % 2) {res = res * a % P;}}return res;}
template<class T>
constexpr T power(T a, ll b) {T res = 1;for (; b; b /= 2, a *= a) {if (b % 2) {res *= a;}}return res;}
constexpr ll mul(ll a, ll b, ll p) {ll res = a * b - ll(1.L * a * b / p) * p;res %= p;if (res < 0) {res += p;}return res;}
template<ll P>
struct MLong {
	ll x;
	constexpr MLong() : x{} {}
	constexpr MLong(ll x) : x{norm(x % getMod())} {}
	static ll Mod;constexpr static ll getMod() {if (P > 0) {return P;} else {return Mod;}}
	constexpr static void setMod(ll Mod_) {Mod = Mod_;}
	constexpr ll norm(ll x) const {if (x < 0) {x += getMod();}if (x >= getMod()) {x -= getMod();}return x;}
	constexpr ll val() const {return x;}
	explicit constexpr operator ll() const {return x;}
	constexpr MLong operator-() const {MLong res;res.x = norm(getMod() - x);return res;}
	constexpr MLong inv() const {assert(x != 0);return power(*this, getMod() - 2);}
	constexpr MLong &operator*=(MLong rhs) & {x = mul(x, rhs.x, getMod());return *this;}
	constexpr MLong &operator+=(MLong rhs) & {x = norm(x + rhs.x);return *this;}
	constexpr MLong &operator-=(MLong rhs) & {x = norm(x - rhs.x);return *this;}
	constexpr MLong &operator/=(MLong rhs) & {return *this *= rhs.inv();}
	friend constexpr MLong operator*(MLong lhs, MLong rhs) {MLong res = lhs;res *= rhs;	return res;}
	friend constexpr MLong operator+(MLong lhs, MLong rhs) {MLong res = lhs;res += rhs;	return res;	}
	friend constexpr MLong operator-(MLong lhs, MLong rhs) {MLong res = lhs;res -= rhs;	return res;	}
	friend constexpr MLong operator/(MLong lhs, MLong rhs) {MLong res = lhs;res /= rhs;	return res;	}
	friend constexpr std::istream &operator>>(std::istream &is, MLong &a) {ll v;is >> v;a = MLong(v);return is;}
	friend constexpr std::ostream &operator<<(std::ostream &os, const MLong &a) {return os << a.val();}
	friend constexpr bool operator==(MLong lhs, MLong rhs) {return lhs.val() == rhs.val();}
	friend constexpr bool operator!=(MLong lhs, MLong rhs) {return lhs.val() != rhs.val();}
	constexpr MLong cbrt() const { return pow((P + P - 1) / 3); }
	constexpr MLong pow(auto k) const {MLong a = x;MLong b = 1;for (; k; k >>= 1) {if (k & 1)b *= a;a *= a;}return b;}
	constexpr MLong sqrt() const {if (pow(P >> 1).x != 1) return 0;MLong a = pow(60);MLong b = pow(119);
		for (int k = 21; k >= 0; --k)if (b.pow(1 << k).x != 1) {a *= MLong(3).pow(P >> (k + 2));b *= MLong(3).pow(P >> (k + 1));}
		return std::min(a.x, P - a.x);}
};
template<>
ll MLong<0LL>::Mod = ll(1E18) + 9;
template<int P>
struct MInt {
	int x;
	constexpr MInt() : x{} {}
	constexpr MInt(ll x) : x{norm(x % getMod())} {}
	static int Mod;
	constexpr static int getMod() {if (P > 0) {return P;}else {return Mod;}	}
	constexpr static void setMod(int Mod_) {Mod = Mod_;}
	constexpr int norm(int x) const {if (x < 0) {x += getMod();}if (x >= getMod()) {x -= getMod();}return x;}
	constexpr int val() const {return x;}
	explicit constexpr operator int() const {return x;}
	constexpr MInt operator-() const {MInt res;res.x = norm(getMod() - x);return res;}
	constexpr MInt inv() const {assert(x != 0);return power(*this, getMod() - 2);}
	constexpr MInt &operator*=(MInt rhs) & {x = 1LL * x * rhs.x % getMod();return *this;	}
	constexpr MInt &operator+=(MInt rhs) & {x = norm(x + rhs.x);return *this;	}
	constexpr MInt &operator-=(MInt rhs) & {x = norm(x - rhs.x);return *this;}
	constexpr MInt &operator/=(MInt rhs) & {return *this *= rhs.inv();}
	friend constexpr MInt operator*(MInt lhs, MInt rhs) {MInt res = lhs;res *= rhs;return res;}
	friend constexpr MInt operator+(MInt lhs, MInt rhs) {MInt res = lhs;res += rhs;	return res;	}
	friend constexpr MInt operator-(MInt lhs, MInt rhs) {MInt res = lhs;res -= rhs;return res;}
	friend constexpr MInt operator/(MInt lhs, MInt rhs) {MInt res = lhs;res /= rhs;return res;}
	friend constexpr std::istream &operator>>(std::istream &is, MInt &a) {ll v;is >> v;a = MInt(v);return is;}
	friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) {return os << a.val();}
	friend constexpr bool operator==(MInt lhs, MInt rhs) {return lhs.val() == rhs.val();}
	friend constexpr bool operator!=(MInt lhs, MInt rhs) {return lhs.val() != rhs.val();}
	constexpr MInt cbrt() const { return pow((P + P - 1) / 3); }
	constexpr MInt pow(auto k) const {MInt a = x;MInt b = 1;for (; k; k >>= 1) {if (k & 1)b *= a;a *= a;}return b;}
	constexpr MInt sqrt() const {if (pow(P >> 1).x != 1) return 0;MInt a = pow(60);MInt b = pow(119);
		for (int k = 21; k >= 0; --k)if (b.pow(1 << k).x != 1) {a *= MInt(3).pow(P >> (k + 2));b *= MInt(3).pow(P >> (k + 1));}
		return std::min(a.x, P - a.x);}
};
template<>
int MInt<0>::Mod = 998244353;
template<int V, int P>
constexpr MInt<P> CInv = MInt<P>(V).inv();
using modint = MInt<P>;
modint fac[N],inv[N],ivv[N];
void __attribute__((constructor))init(){
	fac[0]=fac[1]=1;inv[0]=inv[1]=1;ivv[0]=ivv[1]=1;
	for(int i=2;i<N;++i) fac[i]=fac[i-1]*i;
	for(int i=2;i<N;++i) inv[i]=inv[P%i]*(P-P/i);
	for(int i=2;i<N;++i) ivv[i]=ivv[i-1]*inv[i]; 
	//ivv[N]=MInt(fac[N]).inv();
	//for(int i=N-1;i>=0;--i) ivv[i]=ivv[i+1]*(i+1)%P;
}
void solve(){
	ll n,a;read(n,a);
	vector<ll> sp(n+1);
	ll ans=0;
	forfront(i,1,n) {read(sp[i]);if (sp[i]) ans+=3;}
	priority_queue<ll,vector<ll>,less<ll>> q;
	forfront(i,1,n){
		ll mount=0;
		if (sp[i]==0) mount++;
		if ((i==n?sp[1]:sp[i+1]) ==0) mount++;
		if ((i==1?sp[n]:sp[i-1]) ==0) mount++;
		q.push(mount);
	}
	a=n-a;
	while(a--&&(!q.empty())){
		ans+=q.top();
		q.pop();
	}
	write(ans);
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout<<fixed<<setprecision(4);
	int t=1;
//	init();
//	cin>>t;
	while(t--)
		solve();
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 19ms
memory: 15788kb

input:

5 2
1 0 1 0 1

output:

13

result:

ok 1 number(s): "13"

Test #2:

score: 0
Accepted
time: 21ms
memory: 17188kb

input:

100000 33292
1 1 1 1 0 1 1 0 0 1 1 1 1 1 0 1 0 1 0 1 0 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 0 1 1 1 0 1 0 0 1 1 0 0 0 1 0 1 0 1 0 1 1 0 1 1 1 1 0 1 1 0 1 1 1 0 1 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 1 1 1 1 0 1 0 0 1 0 1 0 1 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 1 0 0 0 0 0 1 1 0 1 0 1 0 1 1 1 0 0...

output:

279236

result:

ok 1 number(s): "279236"

Test #3:

score: 0
Accepted
time: 18ms
memory: 17196kb

input:

100000 91906
1 1 1 1 1 0 1 0 0 0 1 0 0 0 1 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 0 0 1 0 0 1 0 1 0 0 1 1 1 0 0 1 0 0 0 1 1 1 0 0 0 1 0 1 1 0 1 0 0 1 1 0 1 0 1 0 1 1 0 0 0 1 0 0 1 0 1 0 1 1 1 0 1 0 1 1 1 0 1 1 0 0 0 0 1 1 1 1 1 1 1 0 0 0 1 0 1 0 0 1 0 0 1 0 1 0 0 1 0 0 0 0 1 0 1 0 1 1 0 0 1 0...

output:

174297

result:

ok 1 number(s): "174297"

Test #4:

score: 0
Accepted
time: 26ms
memory: 17212kb

input:

100000 1825
0 0 0 1 0 0 1 1 0 0 1 0 0 1 0 0 1 1 0 0 0 1 1 1 0 1 1 1 1 0 1 0 0 0 1 0 0 0 0 1 1 1 1 1 0 0 0 0 0 1 1 0 0 1 1 1 1 0 1 0 0 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 1 1 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 0 1 1 0 1 1 0 1 1 0 1 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 1 0 0 1 0 1 0 1 1 0 0 1 0 0 1 1 0 0 1 0 1 1 1 ...

output:

300000

result:

ok 1 number(s): "300000"

Test #5:

score: 0
Accepted
time: 16ms
memory: 17168kb

input:

100000 36092
0 0 0 0 1 1 0 0 1 1 0 0 1 0 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 0 1 1 0 1 1 1 0 0 0 1 0 0 0 0 0 0 1 1 1 1 1 1 0 0 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 0 0 0 0 1 0 0 0 1 1 0 0 0 1 0 1 0 1 1 0 0 1 0 1 0 0 0 1 0 1 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 1 0 0 1 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 0...

output:

276360

result:

ok 1 number(s): "276360"

Test #6:

score: 0
Accepted
time: 17ms
memory: 17192kb

input:

100000 46012
0 0 0 0 1 0 0 0 1 1 0 1 0 1 0 1 1 1 1 1 1 0 0 1 0 1 1 0 1 1 0 1 1 0 1 0 0 1 0 1 0 1 1 1 1 1 0 0 1 0 1 0 1 1 1 0 1 0 0 0 0 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 1 0 0 1 1 0 0 0 0 1 1 1 0 1 0 1 0 1 1 1 0 1 0 0 1 0 0 0 0 1 1 1 1 0 1 0 1 1 0 0 0 1 0 0 0 0 1 0 0 1 1 1 0 1 0 0 1 0 1 0 1 1 0 1 1 1...

output:

266477

result:

ok 1 number(s): "266477"

Test #7:

score: 0
Accepted
time: 22ms
memory: 17164kb

input:

100000 4625
1 1 1 1 0 1 0 1 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 0 0 0 0 0 1 1 0 0 1 1 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 0 1 1 1 1 0 1 0 1 0 0 1 0 1 1 0 1 0 0 1 0 1 0 0 1 0 1 0 0 1 1 0 1 1 1 0 0 1 0 0 1 1 0 1 0 0 1 0 1 0 1 0 1 0 0 0 1 1 0 0 1 0 0 1 0 0 1 1 0 0 0 0 0 0 0 1 1 0 1 1 1 1 1 1 1 0 1 0 1 0 1 0 0 1 1 ...

output:

300000

result:

ok 1 number(s): "300000"

Test #8:

score: 0
Accepted
time: 26ms
memory: 17220kb

input:

100000 14545
1 1 1 1 1 1 0 1 0 0 1 1 1 1 0 0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 0 1 0 1 1 0 0 0 0 0 0 1 0 0 1 0 1 0 0 1 0 0 1 0 0 1 0 1 0 1 1 1 0 1 1 0 1 1 1 1 1 1 0 1 1 1 0 0 1 1 0 0 1 1 1 0 0 0 1 0 1 1 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 1 1 0 0 1 0 1 0 1 1 1 0 0 0 1 0 0 1 0 1 1 0 1 1 1 1 0 0...

output:

297977

result:

ok 1 number(s): "297977"

Test #9:

score: 0
Accepted
time: 12ms
memory: 17196kb

input:

100000 24465
0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 1 0 1 0 0 1 0 1 1 0 1 0 1 1 0 0 0 0 1 0 0 0 1 0 0 1 1 0 0 0 0 1 1 0 0 0 1 0 1 0 1 1 0 1 1 1 0 0 1 1 0 1 1 0 0 0 0 1 1 0 0 0 0 1 0 1 1 0 1 0 0 1 1 0 0 1 1 1 0 1 1 1 1 0 1 0 1 0 0 1 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 1 1 0 1 1 0 0 0 1 0 1 1 1 0 0 1 0 1 0 0 1 1...

output:

287910

result:

ok 1 number(s): "287910"

Test #10:

score: 0
Accepted
time: 17ms
memory: 17212kb

input:

100000 58732
0 0 0 0 1 1 0 0 0 1 1 0 1 1 0 1 0 0 1 0 0 1 0 1 1 0 1 1 0 1 1 1 0 1 0 1 1 1 0 0 0 1 1 0 1 1 0 0 0 1 0 1 0 1 1 0 1 0 1 0 0 0 1 1 0 0 1 1 1 0 0 1 1 1 1 1 1 1 0 1 1 0 1 0 0 1 0 1 0 1 0 0 0 0 1 0 0 1 1 0 0 0 1 1 0 1 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 1 1 0 1 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 1 0 1...

output:

245071

result:

ok 1 number(s): "245071"

Test #11:

score: 0
Accepted
time: 21ms
memory: 17236kb

input:

100000 22238
1 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 1 0 1 1 0 1 1 1 1 0 0 1 0 1 0 0 1 1 1 1 0 1 0 1 0 0 0 1 1 0 1 0 0 0 1 0 0 1 1 0 0 1 1 1 1 1 1 1 0 1 1 1 0 0 0 1 1 0 1 1 1 1 1 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 1 0 0 1 1 1 0 1 1 0 1 0 1 1 0 1 1 0 0 1 0 1 0 0 1 0 0 1 0 1 0 1 1 1 0 1 1 0 0 1 0 1 1 1 0 1 0 0 1...

output:

290348

result:

ok 1 number(s): "290348"

Test #12:

score: 0
Accepted
time: 23ms
memory: 17276kb

input:

100000 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...

output:

300000

result:

ok 1 number(s): "300000"

Test #13:

score: 0
Accepted
time: 12ms
memory: 17224kb

input:

100000 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

300000

result:

ok 1 number(s): "300000"

Test #14:

score: 0
Accepted
time: 21ms
memory: 17244kb

input:

100000 100000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

output:

0

result:

ok 1 number(s): "0"

Test #15:

score: 0
Accepted
time: 19ms
memory: 17208kb

input:

100000 100000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

300000

result:

ok 1 number(s): "300000"